Submission #68140

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
68140	2018-08-16T06:46:00 Z	MrTEK	Conspiracy (POI11_kon)	C++14	90 / 100	2959 ms	132096 KB

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3+1;
 
int n, dsu[N];
bitset<N> g[N], valid;
 
int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
void merge(int u, int v) {
	if((u = root(u)) == (v = root(v))) return;
	dsu[u] += dsu[v];
	dsu[v] = u;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	fill(dsu, dsu+n, -1);
	vector<int> deg(n+1), ord(n+1);
	deg[n] = -1;
 
	for(int i = 0; i < n; i++) {
		cin >> deg[i];
		for(int j = 0, v; j < deg[i]; j++) {
			cin >> v; --v;
			g[i].set(v);
		}
	}
 
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&] (int i, int j) { return deg[i] > deg[j]; });
	valid[n] = true;
	for(int i = n-1; i >= 0; i--) {
		for(int j = i+1; j < n; j++) if(g[ord[i]][ord[j]]) merge(ord[i], ord[j]);
		valid[ord[i]] = dsu[root(ord[i])] == -1;
	}
 
	int lim = -1;
	bool run = true;
	bitset<N> fin;
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < i; j++) run &= g[ord[i]][ord[j]] || dsu[root(ord[i])] == -1 || dsu[root(ord[j])] == -1;
		if(!run) break;
		if(i == n-1 || (valid[ord[i+1]] && deg[ord[i+1]] != deg[ord[i]])) {
			lim = i;
			for(int k = 0; k <= i; k++) fin.set(ord[k]);
			break;
		} 
	}
 
	if(lim == -1) cout << 0, exit(0);
	int ans = lim < n-1;
	for(int i = 0; i <= lim; i++) ans += (g[ord[i]] | fin) == fin;
	if(lim < n-2) for(int i = lim+1; i < n; i++) ans += g[ord[i]] == fin;
	cout << ans;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	568 KB	Output is correct
4	Correct	3 ms	568 KB	Output is correct
5	Correct	3 ms	568 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	568 KB	Output is correct
2	Correct	2 ms	568 KB	Output is correct
3	Correct	2 ms	568 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	568 KB	Output is correct
2	Correct	3 ms	568 KB	Output is correct
3	Correct	3 ms	740 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	740 KB	Output is correct
2	Correct	6 ms	800 KB	Output is correct
3	Correct	4 ms	880 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	928 KB	Output is correct
2	Correct	9 ms	1100 KB	Output is correct
3	Correct	8 ms	1108 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	2032 KB	Output is correct
2	Correct	70 ms	4992 KB	Output is correct
3	Correct	360 ms	18056 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	18252 KB	Output is correct
2	Correct	102 ms	22400 KB	Output is correct
3	Correct	467 ms	40388 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	43036 KB	Output is correct
2	Correct	246 ms	51852 KB	Output is correct
3	Correct	758 ms	67352 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	140 ms	68188 KB	Output is correct
2	Correct	505 ms	68188 KB	Output is correct
3	Correct	1764 ms	68200 KB	Output is correct

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1138 ms	68688 KB	Output is correct
2	Correct	890 ms	99564 KB	Output is correct
3	Correct	2859 ms	99604 KB	Output is correct
4	Runtime error	2959 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
5	Halted	0 ms	0 KB	-

Submission #68140

Compilation message