oj.uz

Submission #124224

# Submission time Handle Problem Language Result Execution time Memory
124224 2019-07-02T19:30:05 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
18 / 100
 3000 ms 133544 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 short cor[MAXN];
static queue<int> qu;
static int n, m;
static ll x;

static void predfs(int cur) {
	comp[0].insert(cur);
	cor[cur]=comp[0].size()-1;
	short ok=0;
	for(auto viz : g[cur]) {
		if(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]);
	memset(cor, -1, sizeof(cor)); 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;
		// printf("resolvendo %d\n", cur);
		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 : g[leaf]) if(comp[viz].find(cara)!=comp[viz].end()) nleaf=cara;
				for(auto cara : g[nleaf]) if(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];
short cor[MAXN];
queue<int> qu;
int n, m;
ll x, respf, mask;
 
void predfs(int cur) {
	comp[0].insert(cur);
	cor[cur]=comp[0].size()-1;
	short ok=0;
	for(auto viz : g[cur]) {
		if(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);
	for(auto viz : g[cur]) {
		if(mask&(1LL<<cor[viz])) continue;
		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]);
	memset(cor, -1, sizeof(cor)); 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 : g[leaf]) if(comp[viz].find(cara)!=comp[viz].end()) nleaf=cara;
				for(auto cara : g[nleaf]) if(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);
			}
		}
	}
 
	if(V) respf|=(1LL<<cor[P]);
	mask|=(1LL<<cor[P]);
	resolve(P, P);
 
	// printf("mask= %lld // respf= %lld\n", mask, respf);
	return respf;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 25212 KB Output is correct
2 Correct 26 ms 25980 KB Output is correct
3 Correct 28 ms 27268 KB Output is correct
4 Correct 27 ms 25240 KB Output is correct
5 Correct 30 ms 25208 KB Output is correct
6 Correct 26 ms 25716 KB Output is correct
7 Correct 30 ms 26756 KB Output is correct
8 Correct 31 ms 27644 KB Output is correct
9 Correct 28 ms 26940 KB Output is correct
10 Correct 25 ms 25748 KB Output is correct
11 Correct 28 ms 25792 KB Output is correct
12 Correct 25 ms 25152 KB Output is correct
13 Correct 28 ms 27004 KB Output is correct
14 Correct 28 ms 27004 KB Output is correct
15 Correct 28 ms 26492 KB Output is correct
16 Correct 28 ms 26792 KB Output is correct
17 Correct 28 ms 26748 KB Output is correct
18 Correct 28 ms 26508 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 86148 KB Output is correct
2 Correct 253 ms 86396 KB Output is correct
3 Correct 215 ms 86140 KB Output is correct
4 Correct 238 ms 99352 KB Output is correct
5 Correct 247 ms 84596 KB Output is correct
6 Correct 207 ms 84888 KB Output is correct
7 Correct 202 ms 84764 KB Output is correct
8 Correct 203 ms 85744 KB Output is correct
9 Correct 214 ms 88092 KB Output is correct
10 Correct 1044 ms 133544 KB Output is correct
11 Execution timed out 3033 ms 63760 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 25212 KB Output is correct
2 Correct 27 ms 25232 KB Output is correct
3 Correct 25 ms 25204 KB Output is correct
4 Correct 47 ms 34208 KB Output is correct
5 Correct 51 ms 34452 KB Output is correct
6 Correct 55 ms 34328 KB Output is correct
7 Correct 46 ms 34344 KB Output is correct
8 Correct 54 ms 34336 KB Output is correct
9 Correct 176 ms 83844 KB Output is correct
10 Correct 197 ms 83792 KB Output is correct
11 Correct 194 ms 83776 KB Output is correct
12 Correct 25 ms 25084 KB Output is correct
13 Correct 24 ms 25080 KB Output is correct
14 Correct 26 ms 24948 KB Output is correct
15 Correct 24 ms 24988 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 86592 KB Output is correct
2 Correct 218 ms 86908 KB Output is correct
3 Incorrect 217 ms 86204 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 86140 KB Output is correct
2 Correct 220 ms 87164 KB Output is correct
3 Correct 227 ms 86428 KB Output is correct
4 Correct 327 ms 105624 KB Output is correct
5 Correct 211 ms 84720 KB Output is correct
6 Correct 207 ms 84524 KB Output is correct
7 Correct 208 ms 84632 KB Output is correct
8 Correct 259 ms 87960 KB Output is correct
9 Correct 206 ms 84872 KB Output is correct
10 Execution timed out 3030 ms 61856 KB Time limit exceeded
11 Halted 0 ms 0 KB -