oj.uz

Submission #116141

# Submission time Handle Problem Language Result Execution time Memory
116141 2019-06-10T20:23:08 Z cki86201 Conspiracy (POI11_kon) C++11
100 / 100
 2244 ms 120500 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, M;
bitset <5050> E[5050];
int ord[5050], color[5050], deg[5050];

int main() {
	scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		int k; scanf("%d", &k);
		deg[i] = k;
		M += k;
		while(k--) {
			int x; scanf("%d", &x);
			E[i][x] = 1;
		}
	}
	for(int i=1;i<=N;i++) ord[i] = i;
	sort(ord+1, ord+1+N, [&](int x, int y) {
		return deg[x] > deg[y];
	});
	M /= 2;
	if(M == 0 || M == (ll)N * (N - 1) / 2) { printf("%d\n", N); return 0; }
	int cnt[2] = {0, M};
	if(M > 0) {
		int f = 0;
		for(int i=1;i<=N;i++) {
			int v = ord[i];
			for(int j=1;j<=N;j++) if(E[v][j]) {
				if(color[j] == 0) cnt[1]--;
				else cnt[0]++;
			}
			color[v] = 1;
			if(cnt[1] == 0 && cnt[0] == i * (i-1) / 2) {
				f = 1;
				break;
			}
		}
		if(f == 0) {
			puts("0");
			return 0;
		}
	}
	
	int c1 = 0, c2 = 0;
	for(int i=1;i<=N;i++) c1 += (color[i] == 1);
	c2 = N - c1;
	vector <int> w;
	for(int i=1;i<=N;i++) if(color[i] == 0) {
		if(deg[i] == c1) {
			w.pb(i);
		}
	}
	if(szz(w) > 1) {
		printf("%d\n", szz(w) + 1);
		return 0;
	}
	else if(szz(w) == 1) {
		int ans = 1; if(c2 > 1) ++ans;
		for(int i=1;i<=N;i++) if(color[i] == 1 && deg[i] == c1) ++ans;
		printf("%d\n", ans);
	}
	else {
		int ans = 1;
		for(int i=1;i<=N;i++) if(color[i] == 1 && deg[i] == c1 - 1 && c1 > 1) ++ans;
		printf("%d\n", ans);
	}
	
	return 0;
}

Compilation message

kon.cpp: In function 'int main()':
kon.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
kon.cpp:39:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int k; scanf("%d", &k);
          ~~~~~^~~~~~~~~~
kon.cpp:43:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x);
           ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 4 ms 512 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1408 KB Output is correct
2 Correct 61 ms 3956 KB Output is correct
3 Correct 279 ms 14572 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1792 KB Output is correct
2 Correct 84 ms 5416 KB Output is correct
3 Correct 364 ms 19668 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 4820 KB Output is correct
2 Correct 289 ms 10860 KB Output is correct
3 Correct 581 ms 31224 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 7508 KB Output is correct
2 Correct 428 ms 23392 KB Output is correct
3 Correct 1378 ms 72036 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 51064 KB Output is correct
2 Correct 661 ms 34424 KB Output is correct
3 Correct 2082 ms 110712 KB Output is correct
4 Correct 2244 ms 120500 KB Output is correct
5 Correct 3 ms 384 KB Output is correct