oj.uz

Submission #124213

# Submission time Handle Problem Language Result Execution time Memory
124213 2019-07-02T17:33:21 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
10 / 100
 234 ms 89788 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; for(auto cara : g[leaf]) if(comp[viz].find(cara)!=comp[viz].end()) nleaf=cara;
				// printf("leaf= %d  nleaf= %d\n", leaf, nleaf);
				cor[cur]=cor[leaf];
				comp[cur].erase(leaf);
				leaves[cur].erase(viz);
				leaves[cur].erase(leaf);
				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; for(auto cara : g[leaf]) if(comp[viz].find(cara)!=comp[viz].end()) nleaf=cara;
				cor[cur]=cor[leaf];
				comp[cur].erase(leaf);
				leaves[cur].erase(viz);
				leaves[cur].erase(leaf);
				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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25328 KB Output is correct
2 Correct 26 ms 25976 KB Output is correct
3 Correct 32 ms 27240 KB Output is correct
4 Correct 26 ms 25220 KB Output is correct
5 Incorrect 26 ms 25460 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 86000 KB Output is correct
2 Correct 226 ms 87020 KB Output is correct
3 Incorrect 216 ms 87140 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25200 KB Output is correct
2 Correct 25 ms 25200 KB Output is correct
3 Correct 24 ms 25204 KB Output is correct
4 Correct 45 ms 34200 KB Output is correct
5 Correct 47 ms 34300 KB Output is correct
6 Correct 46 ms 34200 KB Output is correct
7 Correct 47 ms 34224 KB Output is correct
8 Correct 47 ms 34224 KB Output is correct
9 Correct 179 ms 83512 KB Output is correct
10 Correct 180 ms 83648 KB Output is correct
11 Correct 191 ms 83664 KB Output is correct
12 Correct 25 ms 24944 KB Output is correct
13 Correct 25 ms 25172 KB Output is correct
14 Correct 24 ms 24952 KB Output is correct
15 Correct 25 ms 25072 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 89788 KB Output is correct
2 Correct 218 ms 86856 KB Output is correct
3 Incorrect 216 ms 86000 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 86932 KB Output is correct
2 Incorrect 218 ms 87988 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -