Submission #29552

#	Time	Username	Problem	Language	Result	Execution time	Memory
29552		khsoo01	Untitled (POI11_kon)	C++11	80 / 100	753 ms	81424 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10