oj.uz

Submission #124087

# Submission time Handle Problem Language Result Execution time Memory
124087 2019-07-02T13:50:04 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
0 / 100
 253 ms 72904 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN=2e5+5;
vector<int> g[MAXN];
short marc[MAXN], cor[MAXN];
set<int> comp[MAXN];
queue<int> qu;
int n, m;
ll x;

bool predfs(int cur) {
	comp[0].insert(cur);
	marc[cur]=1; cor[cur]=comp[0].size()-1;
	bool ok=(comp[0].size()==60);
	for(auto viz : g[cur]) {
		if(marc[viz]) continue;
		if(ok) qu.push(viz);
		if(!ok) ok|=predfs(viz);
	}
	return ok;
}

void dfs(int cur, ll &mask, int p) {
	comp[p].insert(cur);
	mask|=(1LL<<cor[cur]);
	if(comp[p].size()==59) return;
	for(auto viz : g[cur]) {
		if(cor[viz]<0) continue;
		if(mask&(1LL<<cor[viz])) continue;
		dfs(viz, mask, p);
		if(comp[p].size()==59) return;
	}
}

void Joi(int N, int M, int A[], int B[], ll X, 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]); x=X;

	memset(cor, -1, sizeof(cor));
	predfs(0);
	for(int i=1; i<n; i++) if(marc[i]) comp[i]=comp[0];
	// for(int i=1; i<n; i++) printf("cor[%d]= %d\n", i, cor[i]);

	while(!qu.empty()) {
		int cur=qu.front(); qu.pop();
		// printf("cur: %d\n", cur);
		for(auto viz : g[cur]) {
			ll mask=0;
			if(comp[cur].empty()&&cor[viz]>=0) {
				dfs(viz, mask, cur);
				comp[cur].insert(cur);
				mask^=(1LL<<60)-1;
				cor[cur]=__builtin_ctz(mask);
				// printf("cor[%d]= %d // mask %lld\n", cur, cor[cur], mask);
			}
			else if(comp[viz].empty()) qu.push(viz);
		}
		
	}

	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=2e5+5;
static vector<int> g[MAXN];
static short marc[MAXN], cor[MAXN];
static set<int> comp[MAXN];
static queue<int> qu;
static int n, m;
static ll mask, respf;

static bool predfs(int cur) {
	comp[0].insert(cur);
	marc[cur]=1; cor[cur]=comp[0].size()-1;
	bool ok=(comp[0].size()==60);
	for(auto viz : g[cur]) {
		if(marc[viz]) continue;
		if(ok) qu.push(viz);
		if(!ok) ok|=predfs(viz);
	}
	return ok;
}

static void dfs(int cur, ll &mask, int p) {
	comp[p].insert(cur);
	mask|=(1LL<<cor[cur]);
	if(comp[p].size()==59) return;
	for(auto viz : g[cur]) {
		if(cor[viz]<0) continue;
		if(mask&(1LL<<cor[viz])) continue;
		dfs(viz, mask, p);
		if(comp[p].size()==59) return;
	}
}

void responde(int cur, int p) {
	// printf("responde %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]);
		responde(viz, p);
		Move(cur);
	}
}

ll 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(marc[i]) comp[i]=comp[0];
	while(!qu.empty()) {
		int cur=qu.front(); qu.pop();
		for(auto viz : g[cur]) {
			ll mask=0;
			if(comp[cur].empty()&&cor[viz]>=0) {
				dfs(viz, mask, cur);
				comp[cur].insert(cur);
				mask^=(1LL<<60)-1;
				cor[cur]=__builtin_ctz(mask);
			}
			else if(comp[viz].empty()) qu.push(viz);
		}
	}

	if(V) respf|=(1LL<<cor[P]);
	mask=(1LL<<(cor[P]));
	responde(P, P);

	// printf("respf %lld\n", respf);
	return respf;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 30080 KB Output is correct
2 Correct 31 ms 30944 KB Output is correct
3 Incorrect 31 ms 30808 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 72904 KB Output is correct
2 Correct 252 ms 71844 KB Output is correct
3 Incorrect 251 ms 68564 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 30320 KB Output is correct
2 Correct 30 ms 30320 KB Output is correct
3 Incorrect 30 ms 30328 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 239 ms 68868 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 65104 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -