oj.uz

Submission #29552

# Submission time Handle Problem Language Result Execution time Memory
29552 2017-07-20T06:02:30 Z khsoo01 Conspiracy (POI11_kon) C++11
80 / 100
 753 ms 81424 KB 
#include<bits/stdc++.h>
#define rf(x) {(x)=0;while(*pp<48)pp++;while(47<*pp)(x)=((x)<<3)+((x)<<1)+(*pp++&15);}
using namespace std;
const int N = 5005;

static unsigned char str[55555555], *pp = str;

int n, ms, cc, wh[2*N], cnt[N], ans = 1;
bool vis[2*N], adj[N][N], sol[N];

vector<int> st, mem[2];

void dfs (int I, int B) {
	int X = B * n + I;
	if(vis[X]) return;
	vis[X] = true;
	for(int i=1;i<=n;i++) {
		if(I != i && adj[I][i] != B) dfs(i, B^1);
	}
	st.push_back(X);
}

void rdfs (int I, int B) {
	int X = B * n + I;
	if(vis[X]) return;
	vis[X] = true; wh[X] = cc;
	for(int i=1;i<=n;i++) {
		if(I != i && adj[I][i] == B) rdfs(i, B^1);
	}
}

int main()
{
	fread(str, 1, 55555555, stdin);
	rf(n);
	for(int i=1;i<=n;i++) {
		int M, T;
		rf(M);
		ms += M;
		for(int j=0;j<M;j++) {
			rf(T);
			adj[i][T] = 1;
		}
	}
	if(ms == 0 || ms == n*(n-1)) {
		printf("%d\n",n); return 0;
	}
	for(int i=1;i<=n;i++) {
		dfs(i, 0); dfs(i, 1);
	}
	fill(vis+1, vis+1+2*n, 0);
	for(int i=st.size();i--;) {
		int T = st[i];
		if(vis[T]) continue;
		cc++;
		T > n ? rdfs(T-n, 1) : rdfs(T, 0);
	}
	for(int i=1;i<=n;i++) {
		if(wh[i] == wh[i+n]) {puts("0"); return 0;}
		sol[i] = (wh[i] < wh[i+n]);
		mem[sol[i]].push_back(i);
	}
	for(int i=1;i<=n;i++) {
		int B = sol[i]^1;
		for(auto &T : mem[B]) {
			if(adj[i][T] == B) cnt[i]++;
		}
		if(cnt[i] == mem[B].size()) ans++;
	}
	for(auto &A : mem[0]) for(auto &B : mem[1]) {
		if(cnt[A] + cnt[B] == n-1) ans++;
	}
	printf("%d\n",ans);
}

Compilation message

kon.cpp: In function 'int main()':
kon.cpp:68:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(cnt[i] == mem[B].size()) ans++;
             ^
kon.cpp:34:32: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 55555555, stdin);
                                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 80808 KB Output is correct
2 Correct 0 ms 80808 KB Output is correct
3 Correct 0 ms 80808 KB Output is correct
4 Correct 0 ms 80808 KB Output is correct
5 Correct 0 ms 80808 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 80844 KB Output is correct
2 Correct 56 ms 80808 KB Output is correct
3 Correct 73 ms 80808 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 80868 KB Output is correct
2 Correct 79 ms 80808 KB Output is correct
3 Correct 123 ms 80948 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 81132 KB Output is correct
2 Correct 176 ms 80964 KB Output is correct
3 Correct 156 ms 80948 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 81308 KB Output is correct
2 Correct 379 ms 81036 KB Output is correct
3 Runtime error 66 ms 80808 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 81424 KB Output is correct
2 Correct 606 ms 81136 KB Output is correct
3 Runtime error 79 ms 80808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -