oj.uz

Submission #29542

# Submission time Handle Problem Language Result Execution time Memory
29542 2017-07-20T05:49:48 Z 김현수(#1240) Conspiracy (POI11_kon) C++14
80 / 100
 3000 ms 27168 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;

int n, 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()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		int M, T;
		scanf("%d",&M);
		for(int j=0;j<M;j++) {
			scanf("%d",&T);
			adj[i][T] = 1;
		}
	}
	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:59:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(cnt[i] == mem[B].size()) ans++;
             ^
kon.cpp:30:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
kon.cpp:33:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&M);
                 ^
kon.cpp:35:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&T);
                  ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 26556 KB Output is correct
2 Correct 0 ms 26556 KB Output is correct
3 Incorrect 0 ms 26556 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 26596 KB Output is correct
2 Correct 93 ms 26556 KB Output is correct
3 Correct 413 ms 26556 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 26616 KB Output is correct
2 Correct 166 ms 26556 KB Output is correct
3 Correct 636 ms 26696 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 26876 KB Output is correct
2 Correct 436 ms 26708 KB Output is correct
3 Correct 1099 ms 26696 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 27056 KB Output is correct
2 Correct 939 ms 26788 KB Output is correct
3 Correct 2156 ms 26696 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2253 ms 27168 KB Output is correct
2 Correct 1333 ms 26876 KB Output is correct
3 Execution timed out 3000 ms 26696 KB Execution timed out
4 Halted 0 ms 0 KB -