Submission #47210

#	Time	Username	Problem	Language	Result	Execution time	Memory
47210		Bruteforceman	Untitled (POI11_kon)	C++11	90 / 100	3067 ms	131072 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#define link hehehe

char a[5005][5005];
int n;
bitset <10005> g[10005];
int tot;

bool vis[10005];
stack <int> s;
vector <int> scc[10005];
int idg[10005];
int assign[10005];
int sol[10005];

int link[5005];

inline void dfs(int x) {
	vis[x] = true;
	for(int i = 2; i <= tot; i++) {
		if(g[x][i] == 1 && vis[i] == false) {
			dfs(i);
		}
	}
	s.push(x);
}
inline void transpose(int x, int id) {
	scc[id].push_back(x);
	vis[x] = true;
	idg[x] = id;
	for(int i = 2; i <= tot; i++) {
		if(g[i][x] == 1 && vis[i] == false) {
			transpose(i, id);
		}
	}
}

int main(int argc, char const *argv[])
{
	memset(a, 'R', sizeof a);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		int deg;
		scanf("%d", &deg);
		for(int j = 1; j <= deg; j++) {
			int x;
			scanf("%d", &x);
			a[i][x] = a[x][i] = 'G';
			// if(x < i) printf("%d %d\n", x, i);
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			if(a[i][j] == 'G') {
				g[(i << 1) | 1][j << 1] = 1;
				g[(j << 1) | 1][i << 1] = 1;
			} else {
				g[i << 1][(j << 1) | 1] = 1;
				g[j << 1][(i << 1) | 1] = 1;
			}
		}
	}
	tot = (n << 1) | 1; 

	memset(vis, false, sizeof vis);
	for(int i = 2; i <= tot; i++) {
		if(vis[i] == false) dfs(i);
	}

	memset(vis, false, sizeof vis);
	int id = 0;
	while(not s.empty()) {
		int x = s.top();
		s.pop();		
		if(vis[x] == false) {
			transpose(x, ++id);
		}
	}
	for(int i = 1; i <= n; i++) {
		int p = i << 1;
		int q = p | 1;
		if(idg[p] == idg[q]) {
			printf("0\n");
			exit(0);
		}
	}

	memset(assign, -1, sizeof assign);
	for(int i = 1; i <= id; i++) {
		if(assign[i] != -1) continue;
		assign[i] = 0; 
		for(size_t j = 0; j < scc[i].size(); j++) {
			int y = scc[i][j];
			assign[idg[y ^ 1]] = 1; 
		}
	}  

	int setx = 0;
	int sety = 0;
	for(int i = 1; i <= n; i++) {
		if(assign[idg[i << 1]] == 1) {
			sol[i] = 1;
			++setx;
		} else {
			sol[i] = 0;
			++sety;
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(sol[i] == 1 && sol[j] == 0 && a[i][j] == 'R') {
				++link[i];
			} 
			if(sol[i] == 0 && sol[j] == 1 && a[i][j] == 'G') {
				++link[i];
			}
		}
	}
	int ans = 1;
	for(int i = 1; i <= n; i++) {
		if(sol[i] == 1) {
			if(link[i] == sety) ++ans;
		} else {
			if(link[i] == setx) ++ans;
		}
	}
	for(int i = 1; i <= n; i++) {
		if(sol[i] == 0) continue;
		for(int j = 1; j <= n; j++) {
			if(sol[j] == 1) continue;

			if(link[i] == sety-1 && link[j] == setx && a[i][j] == 'G') {
				++ans;
			}
			if(link[i] == sety && link[j] == setx-1 && a[i][j] == 'R') {
				++ans;
			}
		}
	}
	bool redClique = true;
	bool greenClique = true;
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			if(a[i][j] == 'G') redClique = false;
			if(a[i][j] == 'R') greenClique = false;
		}
	}
	ans -= redClique;
	ans -= greenClique;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

kon.cpp: In function 'int main(int, const char**)':
kon.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
kon.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &deg);
   ~~~~~^~~~~~~~~~~~
kon.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~

• 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: 10 / 10
• Subtask 10: 0 / 10