oj.uz

Submission #124284

# Submission time Handle Problem Language Result Execution time Memory
124284 2019-07-03T00:04:03 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
83 / 100
 352 ms 132760 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 unordered_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(abs(prof[cur]-prof[viz])!=1) continue;
			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++;
				cor[cur]=cor[leaf];
				comp[cur].erase(leaf);
				leaves[cur].erase(viz);
				leaves[cur].erase(leaf);
				if(aux==2) leaves[cur].insert(nleaf);
			}
		}
	}
 
	// 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];
unordered_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(abs(prof[cur]-prof[viz])!=1) continue;
			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++;
				cor[cur]=cor[leaf];
				comp[cur].erase(leaf);
				leaves[cur].erase(viz);
				leaves[cur].erase(leaf);
				if(aux==2) leaves[cur].insert(nleaf);
			}
		}
	}
 
	//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;
}

Compilation message

Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:53:22: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cor[cur]=cor[leaf];
              ~~~~~~~~^

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:65:22: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cor[cur]=cor[leaf];
              ~~~~~~~~^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 32756 KB Output is correct
2 Correct 39 ms 33156 KB Output is correct
3 Correct 40 ms 34428 KB Output is correct
4 Correct 35 ms 32668 KB Output is correct
5 Correct 34 ms 32864 KB Output is correct
6 Correct 35 ms 33300 KB Output is correct
7 Correct 38 ms 34176 KB Output is correct
8 Correct 38 ms 34812 KB Output is correct
9 Correct 38 ms 34204 KB Output is correct
10 Correct 35 ms 33200 KB Output is correct
11 Correct 41 ms 33936 KB Output is correct
12 Correct 34 ms 32636 KB Output is correct
13 Correct 38 ms 34300 KB Output is correct
14 Correct 38 ms 34532 KB Output is correct
15 Correct 40 ms 34080 KB Output is correct
16 Correct 40 ms 34004 KB Output is correct
17 Correct 43 ms 34464 KB Output is correct
18 Correct 41 ms 34240 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 90988 KB Output is correct
2 Correct 236 ms 91124 KB Output is correct
3 Correct 239 ms 90968 KB Output is correct
4 Correct 273 ms 106016 KB Output is correct
5 Correct 217 ms 88156 KB Output is correct
6 Correct 224 ms 92832 KB Output is correct
7 Correct 217 ms 88164 KB Output is correct
8 Correct 224 ms 93824 KB Output is correct
9 Correct 226 ms 95124 KB Output is correct
10 Correct 328 ms 132760 KB Output is correct
11 Correct 325 ms 132176 KB Output is correct
12 Correct 244 ms 97080 KB Output is correct
13 Correct 238 ms 95988 KB Output is correct
14 Correct 255 ms 100508 KB Output is correct
15 Correct 230 ms 91592 KB Output is correct
16 Correct 234 ms 93716 KB Output is correct
17 Correct 268 ms 105520 KB Output is correct
18 Correct 348 ms 106784 KB Output is correct
19 Correct 297 ms 104600 KB Output is correct
20 Correct 226 ms 93000 KB Output is correct
21 Correct 209 ms 92192 KB Output is correct
22 Correct 228 ms 92748 KB Output is correct
23 Correct 225 ms 93048 KB Output is correct
24 Correct 242 ms 93024 KB Output is correct
25 Correct 227 ms 93068 KB Output is correct
26 Correct 224 ms 92824 KB Output is correct
27 Correct 220 ms 92824 KB Output is correct
28 Correct 222 ms 93064 KB Output is correct
29 Correct 204 ms 87504 KB Output is correct
30 Correct 223 ms 90180 KB Output is correct
31 Correct 36 ms 33512 KB Output is correct
32 Correct 37 ms 33324 KB Output is correct
33 Correct 41 ms 34972 KB Output is correct
34 Correct 36 ms 33140 KB Output is correct
35 Correct 34 ms 32660 KB Output is correct
36 Correct 34 ms 32708 KB Output is correct
37 Correct 35 ms 32628 KB Output is correct
38 Correct 34 ms 32712 KB Output is correct
39 Correct 34 ms 32560 KB Output is correct
40 Correct 37 ms 32676 KB Output is correct
41 Correct 34 ms 32888 KB Output is correct
42 Correct 35 ms 32844 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 32500 KB Output is correct
2 Correct 37 ms 32628 KB Output is correct
3 Correct 39 ms 32764 KB Output is correct
4 Correct 57 ms 41228 KB Output is correct
5 Correct 57 ms 41256 KB Output is correct
6 Correct 62 ms 41204 KB Output is correct
7 Correct 62 ms 41244 KB Output is correct
8 Correct 62 ms 41120 KB Output is correct
9 Correct 209 ms 87856 KB Output is correct
10 Correct 188 ms 87864 KB Output is correct
11 Correct 194 ms 88192 KB Output is correct
12 Correct 34 ms 32604 KB Output is correct
13 Correct 34 ms 32636 KB Output is correct
14 Correct 37 ms 32504 KB Output is correct
15 Correct 34 ms 32384 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 91120 KB Output is correct
2 Correct 240 ms 90964 KB Output is correct
3 Correct 241 ms 90876 KB Output is correct
4 Correct 267 ms 105112 KB Output is correct
5 Correct 220 ms 88576 KB Output is correct
6 Correct 225 ms 94264 KB Output is correct
7 Correct 223 ms 93080 KB Output is correct
8 Correct 218 ms 89508 KB Output is correct
9 Correct 222 ms 93024 KB Output is correct
10 Correct 352 ms 131516 KB Output is correct
11 Correct 317 ms 127880 KB Output is correct
12 Correct 241 ms 95672 KB Output is correct
13 Correct 240 ms 96380 KB Output is correct
14 Correct 272 ms 99452 KB Output is correct
15 Correct 232 ms 91652 KB Output is correct
16 Correct 275 ms 92212 KB Output is correct
17 Correct 282 ms 105784 KB Output is correct
18 Correct 255 ms 102200 KB Output is correct
19 Correct 296 ms 104872 KB Output is correct
20 Correct 194 ms 93288 KB Output is correct
21 Correct 191 ms 92300 KB Output is correct
22 Correct 222 ms 92940 KB Output is correct
23 Correct 221 ms 92880 KB Output is correct
24 Correct 219 ms 92828 KB Output is correct
25 Correct 217 ms 92840 KB Output is correct
26 Correct 218 ms 93196 KB Output is correct
27 Correct 222 ms 93044 KB Output is correct
28 Correct 222 ms 92696 KB Output is correct
29 Correct 212 ms 87504 KB Output is correct
30 Correct 215 ms 89996 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 90968 KB Output is correct
2 Correct 251 ms 91044 KB Output is correct
3 Correct 271 ms 90888 KB Output is correct
4 Correct 273 ms 107168 KB Output is correct
5 Correct 220 ms 88560 KB Output is correct
6 Correct 217 ms 92832 KB Output is correct
7 Correct 218 ms 93032 KB Output is correct
8 Correct 227 ms 95352 KB Output is correct
9 Correct 221 ms 93056 KB Output is correct
10 Correct 306 ms 130340 KB Output is correct
11 Correct 349 ms 129632 KB Output is correct
12 Correct 244 ms 98032 KB Output is correct
13 Correct 242 ms 98308 KB Output is correct
14 Correct 250 ms 99468 KB Output is correct
15 Correct 268 ms 104608 KB Output is correct
16 Correct 235 ms 92960 KB Output is correct
17 Correct 263 ms 104832 KB Output is correct
18 Correct 273 ms 105508 KB Output is correct
19 Correct 279 ms 107116 KB Output is correct
20 Correct 195 ms 93080 KB Output is correct
21 Correct 195 ms 92084 KB Output is correct
22 Incorrect 220 ms 92856 KB Wrong Answer [7]
23 Halted 0 ms 0 KB -