oj.uz

Submission #124285

# Submission time Handle Problem Language Result Execution time Memory
124285 2019-07-03T00:22:26 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
18 / 100
 513 ms 262144 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(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];
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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 29560 KB Output is correct
2 Correct 31 ms 30336 KB Output is correct
3 Correct 36 ms 31636 KB Output is correct
4 Correct 30 ms 29552 KB Output is correct
5 Correct 30 ms 29816 KB Output is correct
6 Correct 31 ms 30204 KB Output is correct
7 Correct 35 ms 31328 KB Output is correct
8 Correct 36 ms 32264 KB Output is correct
9 Correct 33 ms 31352 KB Output is correct
10 Correct 32 ms 30404 KB Output is correct
11 Correct 38 ms 30756 KB Output is correct
12 Correct 28 ms 29624 KB Output is correct
13 Correct 34 ms 31616 KB Output is correct
14 Correct 36 ms 31352 KB Output is correct
15 Correct 35 ms 31052 KB Output is correct
16 Correct 34 ms 30972 KB Output is correct
17 Correct 35 ms 31480 KB Output is correct
18 Correct 35 ms 31360 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 93220 KB Output is correct
2 Correct 281 ms 93028 KB Output is correct
3 Correct 269 ms 93084 KB Output is correct
4 Correct 287 ms 109780 KB Output is correct
5 Correct 281 ms 90432 KB Output is correct
6 Correct 234 ms 90700 KB Output is correct
7 Runtime error 513 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29424 KB Output is correct
2 Correct 30 ms 29692 KB Output is correct
3 Correct 30 ms 29600 KB Output is correct
4 Correct 60 ms 39056 KB Output is correct
5 Correct 57 ms 38908 KB Output is correct
6 Correct 55 ms 39056 KB Output is correct
7 Correct 60 ms 38928 KB Output is correct
8 Correct 54 ms 39048 KB Output is correct
9 Correct 199 ms 90304 KB Output is correct
10 Correct 200 ms 90244 KB Output is correct
11 Correct 198 ms 90284 KB Output is correct
12 Correct 28 ms 29296 KB Output is correct
13 Correct 28 ms 29660 KB Output is correct
14 Correct 28 ms 29424 KB Output is correct
15 Correct 28 ms 29304 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 93168 KB Output is correct
2 Correct 255 ms 92996 KB Output is correct
3 Correct 250 ms 92992 KB Output is correct
4 Correct 279 ms 108944 KB Output is correct
5 Correct 234 ms 90812 KB Output is correct
6 Correct 266 ms 93096 KB Output is correct
7 Correct 237 ms 90988 KB Output is correct
8 Correct 272 ms 90484 KB Output is correct
9 Correct 274 ms 90608 KB Output is correct
10 Correct 323 ms 139916 KB Output is correct
11 Correct 318 ms 133360 KB Output is correct
12 Correct 262 ms 96816 KB Output is correct
13 Correct 248 ms 97628 KB Output is correct
14 Correct 259 ms 100872 KB Output is correct
15 Correct 235 ms 93748 KB Output is correct
16 Correct 241 ms 94780 KB Output is correct
17 Correct 290 ms 109636 KB Output is correct
18 Correct 265 ms 105804 KB Output is correct
19 Correct 278 ms 107332 KB Output is correct
20 Runtime error 452 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 93080 KB Output is correct
2 Correct 257 ms 93328 KB Output is correct
3 Correct 263 ms 93100 KB Output is correct
4 Correct 291 ms 111104 KB Output is correct
5 Correct 235 ms 90888 KB Output is correct
6 Correct 231 ms 90568 KB Output is correct
7 Correct 229 ms 90560 KB Output is correct
8 Correct 239 ms 94344 KB Output is correct
9 Correct 230 ms 90772 KB Output is correct
10 Correct 322 ms 136972 KB Output is correct
11 Correct 314 ms 137080 KB Output is correct
12 Correct 248 ms 97552 KB Output is correct
13 Correct 250 ms 97636 KB Output is correct
14 Correct 267 ms 100912 KB Output is correct
15 Correct 284 ms 109288 KB Output is correct
16 Correct 240 ms 95592 KB Output is correct
17 Correct 270 ms 107724 KB Output is correct
18 Correct 318 ms 110660 KB Output is correct
19 Correct 281 ms 110128 KB Output is correct
20 Runtime error 451 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -