90pts TLE求助
查看原帖
90pts TLE求助
1045932
AquaDaMean1e楼主2024/9/13 20:22
#include <bits/stdc++.h>
using namespace std;
struct edge {
	int next, ed;
}b[1000010];
struct node {
	int x, step;
};
queue <node> q;
int n, Q, t[1010], nbs[1010], tot;
bool vis1[1010], vis2[1010][1010];
int read () {
	    int x = 0, f = 1;
	    char ch = getchar();
	    while (ch < '0' || ch > '9') {
	        if (ch == '-')
	            f = -1;
	        ch = getchar();
	    }
	    while (ch >= '0' && ch <= '9') {
	        x = (x << 1) + (x << 3) + (ch - '0');
	        ch = getchar();
	    }
	    return x * f;
}
void print (int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
int bfs () {
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		if (!t[i]) {
			q.push({i, 1});
		}
	}
	while (!q.empty()) {
		node cur = q.front();
		ret = max(ret, cur.step);
		for (int k = nbs[cur.x]; k; k = b[k].next) {
			int u = b[k].ed;
			t[u]--;
			if (!t[u]) {
				q.push({u, cur.step + 1});
			}
		}
		q.pop();
	}
	return ret;
}
int main () {
	n = read(), Q = read();
	while (Q--) {
		memset(vis1, 0, sizeof(vis1));
		int s, l, r;
		s = read();
		for (int i = 1, x; i <= s; i++) {
			x = read();
			if (i == 1) {
				l = x;
			}
			if (i == s) {
				r = x;
			}
			vis1[x] = true;
		}
		for (int i = l; i <= r; i++) {
			if (vis1[i]) {
				for (int j = l; j <= r; j++) {
					if (!vis1[j] && !vis2[i][j]) {
						vis2[i][j] = true;
						t[j]++;
						b[++tot].ed = j; b[tot].next = nbs[i]; nbs[i] = tot;
					}
				}
			}
		}
	}
	print(bfs());
	return 0;
}

心态崩了

2024/9/13 20:22
加载中...