oj.uz

Submission #124289

# Submission time Handle Problem Language Result Execution time Memory
124289 2019-07-03T00:38:48 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
100 / 100
 355 ms 141752 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN=1e5+5;
static set<int> g[MAXN];
static set<int> comp[MAXN], leaves[MAXN];
static int cor[MAXN], prof[MAXN];
static queue<int> qu;
static int n, m;
static ll x;
 
static void inicia(int cur) {
	cor[cur]=-1;
	for(auto viz : g[cur]) {
		if(cor[viz]) continue;
		prof[viz]=prof[cur]+1;
		inicia(viz);
	}
}
 
static void predfs(int cur) {
	comp[0].insert(cur);
	cor[cur]=comp[0].size()-1;
	int ok=0;
	for(auto viz : g[cur]) {
		if(abs(prof[cur]-prof[viz])!=1||cor[viz]!=-1) continue;
		if(comp[0].size()<60) predfs(viz), ok++;
		else if(cor[viz]==-1) qu.push(viz);
	}
	if(!ok||(cur==0&&ok==1)) leaves[0].insert(cur);
}
 
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	n=N; m=M; x=X; for(int i=0; i<m; i++) g[A[i]].insert(B[i]), g[B[i]].insert(A[i]);
	inicia(0); predfs(0);
	for(int i=1; i<n; i++) if(cor[i]!=-1) comp[i]=comp[0], leaves[i]=leaves[0];
	while(qu.size()) {
		int cur=qu.front(); qu.pop();
		if(comp[cur].size()) continue;
		for(auto viz : g[cur]) {
			if(cor[viz]==-1) qu.push(viz);
			else if(comp[cur].empty()) {
				comp[cur]=comp[viz]; comp[cur].insert(cur);
				leaves[cur]=leaves[viz]; leaves[cur].insert(cur);
				int leaf; for(auto cara : leaves[viz]) if(cara!=viz) leaf=cara;
				int nleaf, aux=0;
				for(auto cara : comp[viz]) if(abs(prof[cara]-prof[leaf])==1&&g[leaf].find(cara)!=g[leaf].end()) nleaf=cara;
				for(auto cara : comp[viz]) if(abs(prof[cara]-prof[nleaf])==1&&g[nleaf].find(cara)!=g[nleaf].end()) aux++;
				if(aux==2) leaves[cur].insert(nleaf);
				comp[cur].erase(leaf);
				leaves[cur].erase(leaf);
				leaves[cur].erase(viz);
				cor[cur]=cor[leaf];
			}
		}
	}
 
	// for(auto cur : leaves[61]) printf("%d ", cur);
	for(int i=0; i<n; i++) {
		ll mask=0;
		for(auto cara : comp[i]) mask|=(1LL<<cor[cara]);
		if(mask!=(1LL<<60)-1) printf("erro!! %d >> %lld\n", i, mask);
	}
 
	for(int i = 0; i < N; i++) MessageBoard(i, (bool)(x&(1LL<<cor[i])));
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN=1e5+5;
set<int> g[MAXN];
set<int> comp[MAXN], leaves[MAXN];
int cor[MAXN], prof[MAXN];
queue<int> qu;
int n, m;
ll x, respf, mask;
 
void inicia(int cur) {
	cor[cur]=-1;
	for(auto viz : g[cur]) {
		if(cor[viz]) continue;
		prof[viz]=prof[cur]+1;
		inicia(viz);
	}
}
 
void predfs(int cur) {
	comp[0].insert(cur);
	cor[cur]=comp[0].size()-1;
	int ok=0;
	for(auto viz : g[cur]) {
		if(abs(prof[cur]-prof[viz])!=1||cor[viz]!=-1) continue;
		if(comp[0].size()<60) predfs(viz), ok++;
		else if(cor[viz]==-1) qu.push(viz);
	}
	if(!ok||(cur==0&&ok==1)) leaves[0].insert(cur);
}
 
 
void resolve(int cur, int p) {
	// printf("resolve %d\n", cur);
	comp[p].erase(cur);
	for(auto viz : g[cur]) {
		if(comp[p].find(viz)==comp[p].end()) continue;
		if(Move(viz)) respf|=(1LL<<cor[viz]);
		mask|=(1LL<<cor[viz]);
		resolve(viz, p);
		Move(cur);
	}
}
 
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	n=N; m=M; for(int i=0; i<m; i++) g[A[i]].insert(B[i]), g[B[i]].insert(A[i]);
	inicia(0); predfs(0);
	for(int i=1; i<n; i++) if(cor[i]!=-1) comp[i]=comp[0], leaves[i]=leaves[0];
	while(qu.size()) {
		int cur=qu.front(); qu.pop();
		if(comp[cur].size()) continue;
		for(auto viz : g[cur]) {
			if(cor[viz]==-1) qu.push(viz);
			else if(comp[cur].empty()) {
				comp[cur]=comp[viz]; comp[cur].insert(cur);
				leaves[cur]=leaves[viz]; leaves[cur].insert(cur);
				int leaf; for(auto cara : leaves[viz]) if(cara!=viz) leaf=cara;
				int nleaf, aux=0;
				for(auto cara : comp[viz]) if(abs(prof[cara]-prof[leaf])==1&&g[leaf].find(cara)!=g[leaf].end()) nleaf=cara;
				for(auto cara : comp[viz]) if(abs(prof[cara]-prof[nleaf])==1&&g[nleaf].find(cara)!=g[nleaf].end()) aux++;
				if(aux==2) leaves[cur].insert(nleaf);
				comp[cur].erase(leaf);
				leaves[cur].erase(leaf);
				leaves[cur].erase(viz);
				cor[cur]=cor[leaf];
			}
		}
	}
 
	// for(auto cur : comp[P]) printf("%d ", cur); cout << endl;
 
	if(V) respf|=(1LL<<cor[P]);
	mask|=(1LL<<cor[P]);
	resolve(P, P);
 
	// printf("mask= %lld // respf= %lld // %d <> %lld\n", mask, respf, comp[P].size(), *comp[P].begin());
	return respf;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29568 KB Output is correct
2 Correct 30 ms 30396 KB Output is correct
3 Correct 35 ms 31636 KB Output is correct
4 Correct 30 ms 29588 KB Output is correct
5 Correct 30 ms 29660 KB Output is correct
6 Correct 31 ms 30192 KB Output is correct
7 Correct 35 ms 31224 KB Output is correct
8 Correct 35 ms 32128 KB Output is correct
9 Correct 34 ms 31224 KB Output is correct
10 Correct 30 ms 30068 KB Output is correct
11 Correct 38 ms 30760 KB Output is correct
12 Correct 28 ms 29424 KB Output is correct
13 Correct 38 ms 31592 KB Output is correct
14 Correct 34 ms 31616 KB Output is correct
15 Correct 34 ms 31096 KB Output is correct
16 Correct 38 ms 30872 KB Output is correct
17 Correct 38 ms 31488 KB Output is correct
18 Correct 35 ms 31420 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 93300 KB Output is correct
2 Correct 262 ms 93028 KB Output is correct
3 Correct 260 ms 93120 KB Output is correct
4 Correct 282 ms 109876 KB Output is correct
5 Correct 237 ms 90436 KB Output is correct
6 Correct 230 ms 90576 KB Output is correct
7 Correct 229 ms 90452 KB Output is correct
8 Correct 230 ms 91840 KB Output is correct
9 Correct 252 ms 93752 KB Output is correct
10 Correct 329 ms 141752 KB Output is correct
11 Correct 327 ms 140852 KB Output is correct
12 Correct 258 ms 97448 KB Output is correct
13 Correct 253 ms 97836 KB Output is correct
14 Correct 307 ms 102524 KB Output is correct
15 Correct 258 ms 94040 KB Output is correct
16 Correct 273 ms 96568 KB Output is correct
17 Correct 291 ms 111152 KB Output is correct
18 Correct 292 ms 112696 KB Output is correct
19 Correct 283 ms 109648 KB Output is correct
20 Correct 201 ms 90692 KB Output is correct
21 Correct 195 ms 89912 KB Output is correct
22 Correct 234 ms 90632 KB Output is correct
23 Correct 230 ms 90768 KB Output is correct
24 Correct 231 ms 90436 KB Output is correct
25 Correct 237 ms 90684 KB Output is correct
26 Correct 229 ms 90552 KB Output is correct
27 Correct 228 ms 90624 KB Output is correct
28 Correct 232 ms 90612 KB Output is correct
29 Correct 218 ms 85036 KB Output is correct
30 Correct 248 ms 87604 KB Output is correct
31 Correct 37 ms 30408 KB Output is correct
32 Correct 36 ms 30456 KB Output is correct
33 Correct 35 ms 32248 KB Output is correct
34 Correct 33 ms 30104 KB Output is correct
35 Correct 28 ms 29552 KB Output is correct
36 Correct 28 ms 29508 KB Output is correct
37 Correct 28 ms 29560 KB Output is correct
38 Correct 30 ms 29560 KB Output is correct
39 Correct 33 ms 29560 KB Output is correct
40 Correct 31 ms 29600 KB Output is correct
41 Correct 28 ms 29692 KB Output is correct
42 Correct 30 ms 29760 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29688 KB Output is correct
2 Correct 32 ms 29616 KB Output is correct
3 Correct 33 ms 29552 KB Output is correct
4 Correct 61 ms 39016 KB Output is correct
5 Correct 63 ms 39068 KB Output is correct
6 Correct 55 ms 39056 KB Output is correct
7 Correct 53 ms 39176 KB Output is correct
8 Correct 53 ms 39176 KB Output is correct
9 Correct 195 ms 90208 KB Output is correct
10 Correct 199 ms 90348 KB Output is correct
11 Correct 194 ms 90444 KB Output is correct
12 Correct 28 ms 29304 KB Output is correct
13 Correct 28 ms 29560 KB Output is correct
14 Correct 28 ms 29308 KB Output is correct
15 Correct 31 ms 29348 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 93272 KB Output is correct
2 Correct 282 ms 93148 KB Output is correct
3 Correct 254 ms 93228 KB Output is correct
4 Correct 287 ms 109032 KB Output is correct
5 Correct 236 ms 90740 KB Output is correct
6 Correct 256 ms 92736 KB Output is correct
7 Correct 231 ms 91048 KB Output is correct
8 Correct 231 ms 90608 KB Output is correct
9 Correct 229 ms 90740 KB Output is correct
10 Correct 355 ms 140088 KB Output is correct
11 Correct 314 ms 133412 KB Output is correct
12 Correct 247 ms 96896 KB Output is correct
13 Correct 250 ms 97588 KB Output is correct
14 Correct 260 ms 100996 KB Output is correct
15 Correct 235 ms 93844 KB Output is correct
16 Correct 241 ms 94704 KB Output is correct
17 Correct 286 ms 109368 KB Output is correct
18 Correct 300 ms 105920 KB Output is correct
19 Correct 311 ms 107496 KB Output is correct
20 Correct 227 ms 90812 KB Output is correct
21 Correct 200 ms 89656 KB Output is correct
22 Correct 229 ms 90780 KB Output is correct
23 Correct 228 ms 90576 KB Output is correct
24 Correct 238 ms 90604 KB Output is correct
25 Correct 248 ms 90692 KB Output is correct
26 Correct 229 ms 90828 KB Output is correct
27 Correct 243 ms 90680 KB Output is correct
28 Correct 225 ms 90612 KB Output is correct
29 Correct 212 ms 85124 KB Output is correct
30 Correct 222 ms 87736 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 93196 KB Output is correct
2 Correct 256 ms 93176 KB Output is correct
3 Correct 250 ms 93004 KB Output is correct
4 Correct 294 ms 110832 KB Output is correct
5 Correct 231 ms 90880 KB Output is correct
6 Correct 226 ms 90560 KB Output is correct
7 Correct 227 ms 90624 KB Output is correct
8 Correct 236 ms 94500 KB Output is correct
9 Correct 235 ms 90752 KB Output is correct
10 Correct 335 ms 137060 KB Output is correct
11 Correct 353 ms 137360 KB Output is correct
12 Correct 248 ms 97312 KB Output is correct
13 Correct 240 ms 97636 KB Output is correct
14 Correct 261 ms 100816 KB Output is correct
15 Correct 285 ms 109388 KB Output is correct
16 Correct 248 ms 95596 KB Output is correct
17 Correct 278 ms 107916 KB Output is correct
18 Correct 286 ms 110636 KB Output is correct
19 Correct 284 ms 110336 KB Output is correct
20 Correct 198 ms 90724 KB Output is correct
21 Correct 198 ms 89896 KB Output is correct
22 Correct 224 ms 90600 KB Output is correct
23 Correct 234 ms 90876 KB Output is correct
24 Correct 231 ms 90816 KB Output is correct
25 Correct 232 ms 90788 KB Output is correct
26 Correct 231 ms 90732 KB Output is correct
27 Correct 248 ms 91000 KB Output is correct
28 Correct 260 ms 91168 KB Output is correct
29 Correct 239 ms 85388 KB Output is correct
30 Correct 225 ms 87936 KB Output is correct
31 Correct 30 ms 30332 KB Output is correct
32 Correct 31 ms 30572 KB Output is correct
33 Correct 35 ms 32132 KB Output is correct
34 Correct 30 ms 30432 KB Output is correct
35 Correct 30 ms 29564 KB Output is correct
36 Correct 28 ms 29628 KB Output is correct
37 Correct 28 ms 29320 KB Output is correct
38 Correct 28 ms 29596 KB Output is correct
39 Correct 30 ms 29556 KB Output is correct
40 Correct 28 ms 29584 KB Output is correct
41 Correct 28 ms 29812 KB Output is correct
42 Correct 28 ms 29880 KB Output is correct