oj.uz

답안 #29547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29547 2017-07-20T05:55:22 Z 김현수(#1240) Conspiracy (POI11_kon) C++14
90 / 100
 3000 ms 27176 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;

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<=n;i++) {
		int M, T;
		scanf("%d",&M);
		ms += M;
		for(int j=0;j<M;j++) {
			scanf("%d",&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:63: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:36:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&T);
                  ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 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
4 Correct 0 ms 26556 KB Output is correct
5 Correct 0 ms 26556 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 26556 KB Output is correct
2 Correct 3 ms 26556 KB Output is correct
3 Correct 3 ms 26556 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 26596 KB Output is correct
2 Correct 156 ms 26556 KB Output is correct
3 Correct 503 ms 26556 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 26620 KB Output is correct
2 Correct 169 ms 26556 KB Output is correct
3 Correct 576 ms 26696 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 26880 KB Output is correct
2 Correct 439 ms 26712 KB Output is correct
3 Correct 933 ms 26696 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 353 ms 27052 KB Output is correct
2 Correct 923 ms 26780 KB Output is correct
3 Correct 2153 ms 26696 KB Output is correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1899 ms 27176 KB Output is correct
2 Correct 1203 ms 26876 KB Output is correct
3 Execution timed out 3000 ms 26556 KB Execution timed out
4 Halted 0 ms 0 KB -