oj.uz

Submission #132559

# Submission time Handle Problem Language Result Execution time Memory
132559 2019-07-19T07:24:13 Z 구재현(#3206) Friends (BOI17_friends) C++14
37 / 100
 950 ms 640 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2505;
using lint = long long;
using pi = pair<int, int>;

struct disj{
	int pa[MAXN], sz[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
		fill(sz, sz + n + 1, 1);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	int getsz(int x){ return sz[find(x)]; }
	bool uni(int p, int q){
		p = find(p); q = find(q);
		if(p == q) return 0;
		sz[p] += sz[q];
		pa[q] = p; return 1;
	}
}disj;

int n, p, q;
void ass(bool p){
	if(!p){
		puts("detention");
		exit(0);
	}
}

int main(){
	scanf("%d %d %d",&n,&p,&q);
	vector<pi> drg;
	for(int i=0; i<n; i++){
		int z; scanf("%d",&z);
		ass(z < p + q);
		for(int j=0; j<z; j++){
			int w; scanf("%d",&w);
			drg.emplace_back(min(w, i), max(w, i));
		}
	}
	sort(drg.begin(), drg.end());
	ass(drg.size() % 2 == 0);
	vector<pi> edg;
	for(int i=0; i<drg.size(); i+=2){
		ass(drg[i] == drg[i + 1]);
		edg.push_back(drg[i]);
	}
	while(clock() < 0.95 * CLOCKS_PER_SEC){
		random_shuffle(edg.begin(), edg.end());
		disj.init(n);
		for(auto &i : edg){
			if(disj.find(i.first) == disj.find(i.second)) continue;
			if(disj.getsz(i.first) + disj.getsz(i.second) <= p){
				disj.uni(i.first, i.second);
			}
		}
		int deg[MAXN] = {};
		for(auto &i : edg){
			int v = disj.find(i.first);
			int w = disj.find(i.second);
			if(v == w) continue;
			deg[v]++; deg[w]++;
		}
		if(*max_element(deg, deg + n) <= q){
			puts("home");
			vector<int> vect[MAXN];
			set<int> s;
			for(int i=0; i<n; i++){
				s.insert(disj.find(i));
				vect[disj.find(i)].push_back(i);
			}
			cout << s.size() << endl;
			for(auto &i : s){
				cout << vect[i].size() << " ";
				for(auto &j : vect[i]) printf("%d ", j);
				puts("");
			}
			return 0;
		}
	}
	ass(0);
}

Compilation message

friends.cpp: In function 'int main()':
friends.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<drg.size(); i+=2){
               ~^~~~~~~~~~~
friends.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&p,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
friends.cpp:37:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int z; scanf("%d",&z);
          ~~~~~^~~~~~~~~
friends.cpp:40:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int w; scanf("%d",&w);
           ~~~~~^~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 950 ms 476 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 28 ms 456 KB Output is correct
3 Correct 628 ms 504 KB Output is correct
4 Correct 950 ms 420 KB Output is correct
5 Correct 950 ms 460 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 28 ms 456 KB Output is correct
3 Correct 628 ms 504 KB Output is correct
4 Correct 950 ms 420 KB Output is correct
5 Correct 950 ms 460 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Incorrect 950 ms 640 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 950 ms 476 KB Output isn't correct
5 Halted 0 ms 0 KB -