oj.uz

Submission #241133

# Submission time Handle Problem Language Result Execution time Memory
241133 2020-06-23T00:17:19 Z super_j6 Friends (BOI17_friends) C++14
69 / 100
 1000 ms 768 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
#include <stack>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 2500;
int n, x, y;
int id[mxn], vis[mxn], in[mxn], ot[mxn], ud[mxn];
vector<int> g[mxn];
set<int> s[mxn];
stack<int> stk;
int k, kx, ky;

void die(){
	cout << "detention" << endl;
	exit(0);
}

//branch group
void spush(int c){
	ud[c] = 1;
	stk.push(c);
}

int spop(){
	int c = stk.top();
	stk.pop();
	ud[c] = 0;
	return c;
}

bool sol(), solin(), solout();

bool sol(){
	if(kx > x || ky > y || kx + ky + stk.size() > x + y) return 0;
	if(stk.empty()) return 1;
	return solin() || solout();
}

bool solin(){
	int c = spop();
	
	int m = 0;
	kx++, in[c] = 1;
	for(int i : g[c]){
		ky += ot[i];
		if(in[i] || ot[i] || ud[i]) continue;
		m++;
		spush(i);
	}
	
	bool ret = sol();
	
	kx--, in[c] = 0;
	for(int i : g[c]) ky -= ot[i];
	while(m--) spop();
	spush(c);
	
	if(ret){
		vis[c] = 1;
		s[k].insert(c);
	}
	
	return ret;
}

bool solout(){
	int c = spop();
	
	ot[c] = 1;
	for(int i : g[c]) ky += in[i];
	
	bool ret = sol();
	
	ot[c] = 0;
	for(int i : g[c]) ky -= in[i];
	spush(c);
	
	return ret;
}
//end branch group

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> x >> y;
	
	for(int i = 0; i < n; i++){
		int m;
		cin >> m;
		for(int j = 0; j < m; j++){
			int v;
			cin >> v;
			g[i].push_back(v);
		}
	}
	
	for(int i = 0; i < n; i++){
		id[i] = -1;
		sort(g[i].begin(), g[i].end());
		for(int j : g[i]){
			auto it = lower_bound(g[j].begin(), g[j].end(), i);
			if(it == g[j].end() || *it != i) die();
		}
	}
	
	memset(id, -1, sizeof(id));
	for(; k < n; k++){
		if(vis[k]) continue;
		
		spush(k);
		if(!solin()) die();
		spop();
		
		for(int i : s[k]){
			int m = id[i];
			if(~m && m != k){
				vector<int> v;
				for(int j  : s[k]){
					if(id[j] == m){
						v.push_back(j);
						s[k].erase(j);
						s[m].erase(j);
						id[j] = -1;
					} 
				} 
				
				int w = 0, z = 0;
				for(int j : v)
				for(int l : g[j]){
					w += id[j] == k;
					z += id[j] == m;
				}
				
				for(int j : v){
					if(w > z){
						id[j] = k;
						s[k].insert(j);
					}else{
						id[j] = m;
						s[m].insert(j);
					}
				}
			}else{
				id[i] = k;
			}
		}
	}
	
	cout << "home" << endl;
	
	int ret = 0;
	for(int i = 0; i < k; i++) ret += !s[i].empty();
	
	cout << ret << endl;
	for(int i = 0; i < k; i++){
		if(s[i].empty()) continue;
		cout << s[i].size();
		for(int j : s[i]) cout << " " << j;
		cout << endl;
	}
	

	return 0;
}

Compilation message

friends.cpp: In function 'bool sol()':
friends.cpp:44:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(kx > x || ky > y || kx + ky + stk.size() > x + y) return 0;
                         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:140:13: warning: unused variable 'l' [-Wunused-variable]
     for(int l : g[j]){
             ^

Subtask #1
20.0 / 20.0

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

Subtask #2
37.0 / 37.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 6 ms 768 KB Output is correct
14 Correct 8 ms 640 KB Output is correct
15 Correct 6 ms 640 KB Output is correct
16 Correct 6 ms 640 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 5 ms 512 KB Output is correct
18 Correct 6 ms 640 KB Output is correct
19 Correct 6 ms 640 KB Output is correct
20 Correct 7 ms 640 KB Output is correct
21 Correct 6 ms 768 KB Output is correct
22 Correct 8 ms 640 KB Output is correct
23 Correct 6 ms 640 KB Output is correct
24 Correct 6 ms 640 KB Output is correct
25 Correct 5 ms 512 KB Output is correct
26 Execution timed out 1093 ms 768 KB Time limit exceeded
27 Halted 0 ms 0 KB -