oj.uz

Submission #124226

# Submission time Handle Problem Language Result Execution time Memory
124226 2019-07-02T20:00:54 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
18 / 100
 3000 ms 124608 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 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]].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];
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]].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;
}

Compilation message

Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:51:57: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     for(auto cara : g[leaf]) if(abs(prof[cara]-prof[leaf])==1&&comp[viz].find(cara)!=comp[viz].end()) nleaf=cara;
                                                ~~~~~~~~~^

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:63:57: warning: 'leaf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     for(auto cara : g[leaf]) if(abs(prof[cara]-prof[leaf])==1&&comp[viz].find(cara)!=comp[viz].end()) nleaf=cara;
                                                ~~~~~~~~~^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 27888 KB Output is correct
2 Correct 32 ms 28528 KB Output is correct
3 Correct 34 ms 29696 KB Output is correct
4 Correct 30 ms 28120 KB Output is correct
5 Correct 30 ms 28024 KB Output is correct
6 Correct 32 ms 28276 KB Output is correct
7 Correct 37 ms 29176 KB Output is correct
8 Correct 46 ms 30072 KB Output is correct
9 Correct 39 ms 29548 KB Output is correct
10 Correct 32 ms 28272 KB Output is correct
11 Correct 35 ms 28452 KB Output is correct
12 Correct 30 ms 27760 KB Output is correct
13 Correct 35 ms 29712 KB Output is correct
14 Correct 34 ms 29560 KB Output is correct
15 Correct 35 ms 29084 KB Output is correct
16 Correct 34 ms 29176 KB Output is correct
17 Correct 34 ms 29208 KB Output is correct
18 Correct 34 ms 29048 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 82608 KB Output is correct
2 Correct 219 ms 82752 KB Output is correct
3 Correct 219 ms 82608 KB Output is correct
4 Correct 244 ms 97048 KB Output is correct
5 Correct 207 ms 81724 KB Output is correct
6 Correct 216 ms 86844 KB Output is correct
7 Correct 206 ms 83256 KB Output is correct
8 Correct 213 ms 87704 KB Output is correct
9 Correct 217 ms 88892 KB Output is correct
10 Execution timed out 3025 ms 60300 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27764 KB Output is correct
2 Correct 31 ms 28016 KB Output is correct
3 Correct 30 ms 27920 KB Output is correct
4 Correct 51 ms 36312 KB Output is correct
5 Correct 49 ms 36248 KB Output is correct
6 Correct 50 ms 36112 KB Output is correct
7 Correct 51 ms 36264 KB Output is correct
8 Correct 53 ms 36324 KB Output is correct
9 Correct 176 ms 81512 KB Output is correct
10 Correct 182 ms 81600 KB Output is correct
11 Correct 179 ms 81464 KB Output is correct
12 Correct 28 ms 27796 KB Output is correct
13 Correct 30 ms 27800 KB Output is correct
14 Correct 30 ms 27824 KB Output is correct
15 Correct 28 ms 27848 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 84336 KB Output is correct
2 Correct 213 ms 82672 KB Output is correct
3 Correct 213 ms 82756 KB Output is correct
4 Correct 258 ms 100336 KB Output is correct
5 Correct 200 ms 82180 KB Output is correct
6 Correct 211 ms 88384 KB Output is correct
7 Correct 207 ms 87024 KB Output is correct
8 Correct 199 ms 83292 KB Output is correct
9 Correct 220 ms 86672 KB Output is correct
10 Execution timed out 3043 ms 62012 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 82496 KB Output is correct
2 Correct 211 ms 82760 KB Output is correct
3 Correct 215 ms 82508 KB Output is correct
4 Correct 259 ms 100888 KB Output is correct
5 Correct 201 ms 83792 KB Output is correct
6 Correct 203 ms 83568 KB Output is correct
7 Correct 210 ms 86712 KB Output is correct
8 Correct 211 ms 88952 KB Output is correct
9 Correct 204 ms 86792 KB Output is correct
10 Execution timed out 4030 ms 124608 KB Time limit exceeded
11 Halted 0 ms 0 KB -