Submission #116141

#	Time	Username	Problem	Language	Result	Execution time	Memory
116141		cki86201	Untitled (POI11_kon)	C++11	100 / 100	2244 ms	120500 KiB

Main

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

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 / 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: 10 / 10