oj.uz

Submission #29556

# Submission time Handle Problem Language Result Execution time Memory
29556 2017-07-20T06:06:52 Z khsoo01 Conspiracy (POI11_kon) C++11
100 / 100
 2489 ms 81428 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()
{
	scanf("%d",&n);
	for(int i=1;i<2*n/3;i++) {
		int M, T;
		scanf("%d",&M);
		ms += M;
		for(int j=0;j<M;j++) {
			scanf("%d",&T);
			adj[i][T] = 1;
		}
	}
	fflush(stdin);
	fread(str, 1, 55555555, stdin);
	for(int i=2*n/3;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:78:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(cnt[i] == mem[B].size()) ans++;
             ^
kon.cpp:34:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
kon.cpp:37:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&M);
                 ^
kon.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&T);
                  ^
kon.cpp:45: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 80812 KB Output is correct
2 Correct 0 ms 80812 KB Output is correct
3 Correct 0 ms 80812 KB Output is correct
4 Correct 0 ms 80812 KB Output is correct
5 Correct 0 ms 80812 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 80852 KB Output is correct
2 Correct 83 ms 80812 KB Output is correct
3 Correct 273 ms 80812 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 80876 KB Output is correct
2 Correct 153 ms 80812 KB Output is correct
3 Correct 419 ms 80952 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 81136 KB Output is correct
2 Correct 323 ms 80964 KB Output is correct
3 Correct 589 ms 80952 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 81312 KB Output is correct
2 Correct 769 ms 81040 KB Output is correct
3 Correct 1466 ms 80952 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1583 ms 81428 KB Output is correct
2 Correct 1073 ms 81132 KB Output is correct
3 Correct 2489 ms 80952 KB Output is correct
4 Correct 2379 ms 80812 KB Output is correct
5 Correct 0 ms 80812 KB Output is correct