oj.uz

Submission #124091

# Submission time Handle Problem Language Result Execution time Memory
124091 2019-07-02T14:01:06 Z wilwxk Amusement Park (JOI17_amusement_park) C++14
28 / 100
 354 ms 88080 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_ctzll(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_ctzll(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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 30312 KB Output is correct
2 Correct 33 ms 30712 KB Output is correct
3 Correct 35 ms 31480 KB Output is correct
4 Correct 30 ms 30348 KB Output is correct
5 Correct 32 ms 30452 KB Output is correct
6 Correct 32 ms 30708 KB Output is correct
7 Correct 36 ms 31464 KB Output is correct
8 Correct 34 ms 31356 KB Output is correct
9 Correct 35 ms 31416 KB Output is correct
10 Correct 32 ms 30640 KB Output is correct
11 Correct 37 ms 31036 KB Output is correct
12 Correct 30 ms 30084 KB Output is correct
13 Correct 35 ms 31620 KB Output is correct
14 Correct 36 ms 31492 KB Output is correct
15 Correct 36 ms 31492 KB Output is correct
16 Correct 34 ms 31488 KB Output is correct
17 Correct 35 ms 31736 KB Output is correct
18 Correct 34 ms 31356 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 84128 KB Output is correct
2 Correct 338 ms 85368 KB Output is correct
3 Correct 354 ms 84984 KB Output is correct
4 Correct 274 ms 88012 KB Output is correct
5 Correct 274 ms 87952 KB Output is correct
6 Correct 269 ms 87812 KB Output is correct
7 Correct 266 ms 87708 KB Output is correct
8 Correct 267 ms 87760 KB Output is correct
9 Correct 265 ms 87720 KB Output is correct
10 Correct 245 ms 88080 KB Output is correct
11 Correct 269 ms 87840 KB Output is correct
12 Correct 271 ms 82668 KB Output is correct
13 Correct 252 ms 82048 KB Output is correct
14 Correct 262 ms 85196 KB Output is correct
15 Correct 261 ms 87804 KB Output is correct
16 Correct 270 ms 87708 KB Output is correct
17 Correct 273 ms 87948 KB Output is correct
18 Correct 275 ms 87948 KB Output is correct
19 Correct 274 ms 87760 KB Output is correct
20 Correct 201 ms 87964 KB Output is correct
21 Correct 197 ms 87036 KB Output is correct
22 Correct 268 ms 87772 KB Output is correct
23 Correct 266 ms 87948 KB Output is correct
24 Correct 281 ms 87948 KB Output is correct
25 Correct 264 ms 87952 KB Output is correct
26 Correct 288 ms 87896 KB Output is correct
27 Correct 264 ms 88048 KB Output is correct
28 Correct 264 ms 87956 KB Output is correct
29 Correct 244 ms 82664 KB Output is correct
30 Correct 253 ms 84984 KB Output is correct
31 Correct 31 ms 30604 KB Output is correct
32 Correct 32 ms 30848 KB Output is correct
33 Correct 33 ms 31484 KB Output is correct
34 Correct 31 ms 30588 KB Output is correct
35 Correct 28 ms 30332 KB Output is correct
36 Correct 30 ms 30332 KB Output is correct
37 Correct 28 ms 30204 KB Output is correct
38 Correct 28 ms 30084 KB Output is correct
39 Correct 28 ms 30076 KB Output is correct
40 Correct 31 ms 30292 KB Output is correct
41 Correct 30 ms 30324 KB Output is correct
42 Correct 28 ms 30212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 30320 KB Output is correct
2 Correct 30 ms 30300 KB Output is correct
3 Correct 30 ms 30456 KB Output is correct
4 Correct 56 ms 39072 KB Output is correct
5 Correct 55 ms 38968 KB Output is correct
6 Correct 56 ms 38968 KB Output is correct
7 Correct 55 ms 38944 KB Output is correct
8 Correct 56 ms 39152 KB Output is correct
9 Correct 197 ms 86936 KB Output is correct
10 Correct 197 ms 86952 KB Output is correct
11 Correct 197 ms 87172 KB Output is correct
12 Correct 28 ms 30068 KB Output is correct
13 Correct 32 ms 30332 KB Output is correct
14 Correct 30 ms 30108 KB Output is correct
15 Correct 33 ms 30320 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 85696 KB Output is correct
2 Correct 352 ms 86352 KB Output is correct
3 Incorrect 325 ms 85444 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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