oj.uz

Submission #124225

# Submission time Handle Problem Language Result Execution time Memory
124225 2019-07-02T19:57:44 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
18 / 100
 3000 ms 133072 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN=1e5+5;
static vector<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]].push_back(B[i]), g[B[i]].push_back(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 : g[leaf]) if(abs(prof[cara]-prof[leaf])==1&&comp[viz].find(cara)!=comp[viz].end()) nleaf=cara;
				for(auto cara : g[nleaf]) if(abs(prof[cara]-prof[nleaf])==1&&comp[viz].find(cara)!=comp[viz].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;
vector<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]].push_back(B[i]), g[B[i]].push_back(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 : g[leaf]) if(abs(prof[cara]-prof[leaf])==1&&comp[viz].find(cara)!=comp[viz].end()) nleaf=cara;
				for(auto cara : g[nleaf]) if(abs(prof[cara]-prof[nleaf])==1&&comp[viz].find(cara)!=comp[viz].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 28 ms 24824 KB Output is correct
2 Correct 24 ms 25456 KB Output is correct
3 Correct 28 ms 26872 KB Output is correct
4 Correct 28 ms 24872 KB Output is correct
5 Correct 28 ms 25004 KB Output is correct
6 Correct 27 ms 25456 KB Output is correct
7 Correct 35 ms 26192 KB Output is correct
8 Correct 38 ms 27508 KB Output is correct
9 Correct 28 ms 26736 KB Output is correct
10 Correct 26 ms 25512 KB Output is correct
11 Correct 28 ms 25468 KB Output is correct
12 Correct 24 ms 24936 KB Output is correct
13 Correct 28 ms 26624 KB Output is correct
14 Correct 28 ms 26752 KB Output is correct
15 Correct 28 ms 26232 KB Output is correct
16 Correct 28 ms 26584 KB Output is correct
17 Correct 27 ms 26372 KB Output is correct
18 Correct 27 ms 26360 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 85056 KB Output is correct
2 Correct 212 ms 85232 KB Output is correct
3 Correct 248 ms 85440 KB Output is correct
4 Correct 278 ms 99044 KB Output is correct
5 Correct 215 ms 84412 KB Output is correct
6 Correct 205 ms 84604 KB Output is correct
7 Correct 205 ms 84356 KB Output is correct
8 Correct 209 ms 85664 KB Output is correct
9 Correct 212 ms 88192 KB Output is correct
10 Correct 1145 ms 133072 KB Output is correct
11 Execution timed out 3060 ms 62212 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24688 KB Output is correct
2 Correct 24 ms 24944 KB Output is correct
3 Correct 24 ms 25080 KB Output is correct
4 Correct 45 ms 33976 KB Output is correct
5 Correct 47 ms 34064 KB Output is correct
6 Correct 46 ms 34324 KB Output is correct
7 Correct 46 ms 34196 KB Output is correct
8 Correct 45 ms 33936 KB Output is correct
9 Correct 178 ms 84196 KB Output is correct
10 Correct 174 ms 84032 KB Output is correct
11 Correct 179 ms 84124 KB Output is correct
12 Correct 24 ms 24700 KB Output is correct
13 Correct 26 ms 24816 KB Output is correct
14 Correct 24 ms 24756 KB Output is correct
15 Correct 25 ms 24688 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 85184 KB Output is correct
2 Correct 237 ms 85312 KB Output is correct
3 Correct 221 ms 85388 KB Output is correct
4 Correct 311 ms 105120 KB Output is correct
5 Correct 209 ms 84632 KB Output is correct
6 Correct 234 ms 86948 KB Output is correct
7 Correct 218 ms 85220 KB Output is correct
8 Correct 216 ms 84504 KB Output is correct
9 Correct 206 ms 84864 KB Output is correct
10 Execution timed out 3074 ms 62620 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 85264 KB Output is correct
2 Correct 237 ms 85184 KB Output is correct
3 Correct 222 ms 85352 KB Output is correct
4 Correct 266 ms 105208 KB Output is correct
5 Correct 217 ms 84992 KB Output is correct
6 Correct 216 ms 84564 KB Output is correct
7 Correct 206 ms 84464 KB Output is correct
8 Correct 214 ms 88304 KB Output is correct
9 Correct 201 ms 84664 KB Output is correct
10 Execution timed out 3054 ms 59428 KB Time limit exceeded
11 Halted 0 ms 0 KB -