oj.uz

Submission #124212

# Submission time Handle Problem Language Result Execution time Memory
124212 2019-07-02T17:25:59 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
10 / 100
 259 ms 90100 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) {
	// printf("resolve %d\n", cur);
	for(auto viz : g[cur]) {
		if(mask&(1LL<<cor[viz])) continue;
		if(comp[cur].find(viz)==comp[cur].end()) continue;
		if(Move(viz)) respf|=(1LL<<cor[viz]);
		mask|=(1LL<<cor[viz]);
		resolve(viz);
		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);

	// 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 25376 KB Output is correct
2 Correct 27 ms 25972 KB Output is correct
3 Correct 31 ms 27408 KB Output is correct
4 Correct 25 ms 25244 KB Output is correct
5 Incorrect 26 ms 25408 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 86372 KB Output is correct
2 Correct 230 ms 87428 KB Output is correct
3 Incorrect 226 ms 87288 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25204 KB Output is correct
2 Correct 26 ms 25204 KB Output is correct
3 Correct 26 ms 25204 KB Output is correct
4 Correct 48 ms 34400 KB Output is correct
5 Correct 47 ms 34444 KB Output is correct
6 Correct 48 ms 34344 KB Output is correct
7 Correct 48 ms 34208 KB Output is correct
8 Correct 48 ms 34224 KB Output is correct
9 Correct 178 ms 83736 KB Output is correct
10 Correct 179 ms 83692 KB Output is correct
11 Correct 176 ms 83864 KB Output is correct
12 Correct 25 ms 25076 KB Output is correct
13 Correct 26 ms 25084 KB Output is correct
14 Correct 26 ms 25028 KB Output is correct
15 Correct 25 ms 24976 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 90100 KB Output is correct
2 Correct 225 ms 87308 KB Output is correct
3 Incorrect 223 ms 86272 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 87300 KB Output is correct
2 Incorrect 259 ms 88336 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -