oj.uz

Submission #124221

# Submission time Handle Problem Language Result Execution time Memory
124221 2019-07-02T19:06:15 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
10 / 100
 414 ms 262148 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, 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25212 KB Output is correct
2 Correct 27 ms 25880 KB Output is correct
3 Correct 30 ms 27296 KB Output is correct
4 Correct 26 ms 25212 KB Output is correct
5 Incorrect 26 ms 25540 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 86356 KB Output is correct
2 Correct 218 ms 87160 KB Output is correct
3 Correct 219 ms 87280 KB Output is correct
4 Incorrect 250 ms 104432 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25076 KB Output is correct
2 Correct 24 ms 25204 KB Output is correct
3 Correct 25 ms 25184 KB Output is correct
4 Correct 47 ms 34520 KB Output is correct
5 Correct 44 ms 34316 KB Output is correct
6 Correct 44 ms 34080 KB Output is correct
7 Correct 51 ms 34348 KB Output is correct
8 Correct 46 ms 34208 KB Output is correct
9 Correct 178 ms 83876 KB Output is correct
10 Correct 175 ms 83736 KB Output is correct
11 Correct 178 ms 83896 KB Output is correct
12 Correct 25 ms 24948 KB Output is correct
13 Correct 26 ms 25180 KB Output is correct
14 Correct 25 ms 24884 KB Output is correct
15 Correct 26 ms 25284 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 89840 KB Output is correct
2 Correct 253 ms 87280 KB Output is correct
3 Incorrect 257 ms 86512 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 87024 KB Output is correct
2 Correct 220 ms 88048 KB Output is correct
3 Correct 214 ms 86512 KB Output is correct
4 Correct 296 ms 110512 KB Output is correct
5 Runtime error 414 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -