oj.uz

Submission #124174

# Submission time Handle Problem Language Result Execution time Memory
124174 2019-07-02T15:20:48 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
10 / 100
 223 ms 89664 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++) printf("%d ", cor[i]);

	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 25212 KB Output is correct
2 Correct 28 ms 25852 KB Output is correct
3 Correct 31 ms 27268 KB Output is correct
4 Correct 27 ms 25244 KB Output is correct
5 Incorrect 27 ms 25464 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 85952 KB Output is correct
2 Correct 220 ms 87408 KB Output is correct
3 Incorrect 218 ms 87296 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 25080 KB Output is correct
2 Correct 26 ms 25204 KB Output is correct
3 Correct 26 ms 25188 KB Output is correct
4 Correct 48 ms 34236 KB Output is correct
5 Correct 47 ms 34080 KB Output is correct
6 Correct 48 ms 34620 KB Output is correct
7 Correct 48 ms 34464 KB Output is correct
8 Correct 48 ms 34236 KB Output is correct
9 Correct 164 ms 83916 KB Output is correct
10 Correct 172 ms 83784 KB Output is correct
11 Correct 163 ms 83852 KB Output is correct
12 Correct 26 ms 24948 KB Output is correct
13 Correct 26 ms 25076 KB Output is correct
14 Correct 24 ms 24948 KB Output is correct
15 Correct 25 ms 24956 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 89664 KB Output is correct
2 Correct 213 ms 87320 KB Output is correct
3 Incorrect 208 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 208 ms 86928 KB Output is correct
2 Incorrect 207 ms 88068 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -