oj.uz

Submission #47210

# Submission time Handle Problem Language Result Execution time Memory
47210 2018-04-29T06:40:41 Z Bruteforceman Conspiracy (POI11_kon) C++11
90 / 100
 3000 ms 131072 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 25080 KB Output is correct
2 Correct 19 ms 25192 KB Output is correct
3 Correct 19 ms 25192 KB Output is correct
4 Correct 19 ms 25252 KB Output is correct
5 Correct 19 ms 25344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 25456 KB Output is correct
2 Correct 20 ms 25464 KB Output is correct
3 Correct 19 ms 25596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 25744 KB Output is correct
2 Correct 20 ms 25744 KB Output is correct
3 Correct 19 ms 25744 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25856 KB Output is correct
2 Correct 24 ms 26144 KB Output is correct
3 Correct 21 ms 26144 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 26296 KB Output is correct
2 Correct 26 ms 26520 KB Output is correct
3 Correct 24 ms 26544 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 29576 KB Output is correct
2 Correct 174 ms 32780 KB Output is correct
3 Correct 647 ms 46684 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 46684 KB Output is correct
2 Correct 266 ms 51248 KB Output is correct
3 Correct 771 ms 69948 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 73128 KB Output is correct
2 Correct 601 ms 82356 KB Output is correct
3 Correct 1180 ms 111808 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 119416 KB Output is correct
2 Correct 1452 ms 131072 KB Output is correct
3 Correct 2907 ms 131072 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2838 ms 131072 KB Output is correct
2 Correct 2322 ms 131072 KB Output is correct
3 Execution timed out 3067 ms 131072 KB Time limit exceeded
4 Halted 0 ms 0 KB -