oj.uz

Submission #91467

# Submission time Handle Problem Language Result Execution time Memory
91467 2018-12-27T15:44:00 Z tmwilliamlin168 Amusement Park (JOI17_amusement_park) C++14
100 / 100
 215 ms 78940 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e4;
static int p[mxN], r[mxN];
static vector<int> adj[mxN], c[mxN];
static vector<vector<int>> d[mxN];
static long long x;

static int find(int x) {
	return x==p[x]?x:(p[x]=find(p[x]));
}

static bool join(int x, int y) {
	if((x=find(x))==(y=find(y)))
		return 0;
	if(r[x]<r[y])
		swap(x, y);
	p[y]=x;
	r[x]+=r[x]==r[y];
	return 1;
}

static void dfs1(int u=0, int p=0) {
	if(c[0].size()>=60)
		return;
	MessageBoard(u, x>>(c[0].size())&1);
	c[0].push_back(u);
	d[0].push_back({});
	if(u) {
		d[0][find(c[0].begin(), c[0].end(), p)-c[0].begin()].push_back(u);
		d[0].back().push_back(p);
	}
	for(int v : adj[u])
		if(v!=p)
			dfs1(v, u);
}

static void dfs2(int u=0, int p=0) {
	c[u]=c[p];
	d[u]=d[p];
	if(find(c[u].begin(), c[u].end(), u)==c[u].end()) {
		for(int i=0; i<60; ++i) {
			if(d[u][i].size()>1||c[u][i]==p)
				continue;
			int j=find(c[u].begin(), c[u].end(), d[u][i][0])-c[u].begin();
			d[u][j].erase(find(d[u][j].begin(), d[u][j].end(), c[u][i]));
			MessageBoard(u, x>>i&1);
			c[u][i]=u;
			d[u][i][0]=p;
			d[u][find(c[u].begin(), c[u].end(), p)-c[u].begin()].push_back(u);
			break;
		}
	}
	for(int v : adj[u])
		if(v!=p)
			dfs2(v, u);
}

void Joi(int n, int m, int a[], int b[], long long X, int t) {
	x=X;
	for(int i=0; i<n; ++i)
		p[i]=i;
	while(m--) {
		if(join(a[m], b[m])) {
			adj[a[m]].push_back(b[m]);
			adj[b[m]].push_back(a[m]);
		}
	}
	dfs1();
	dfs2();
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e4;
int p[mxN], r[mxN], s;
vector<int> adj[mxN], c[mxN];
vector<vector<int>> d[mxN];
long long ans;

int find(int x) {
	return x==p[x]?x:(p[x]=find(p[x]));
}

bool join(int x, int y) {
	if((x=find(x))==(y=find(y)))
		return 0;
	if(r[x]<r[y])
		swap(x, y);
	p[y]=x;
	r[x]+=r[x]==r[y];
	return 1;
}

void dfs1(int u=0, int p=0) {
	if(c[0].size()>=60)
		return;
	c[0].push_back(u);
	d[0].push_back({});
	if(u) {
		d[0][find(c[0].begin(), c[0].end(), p)-c[0].begin()].push_back(u);
		d[0].back().push_back(p);
	}
	for(int v : adj[u])
		if(v!=p)
			dfs1(v, u);
}

void dfs2(int u=0, int p=0) {
	c[u]=c[p];
	d[u]=d[p];
	if(find(c[u].begin(), c[u].end(), u)==c[u].end()) {
		for(int i=0; i<60; ++i) {
			if(d[u][i].size()>1||c[u][i]==p)
				continue;
			int j=find(c[u].begin(), c[u].end(), d[u][i][0])-c[u].begin();
			d[u][j].erase(find(d[u][j].begin(), d[u][j].end(), c[u][i]));
			c[u][i]=u;
			d[u][i][0]=p;
			d[u][find(c[u].begin(), c[u].end(), p)-c[u].begin()].push_back(u);
			break;
		}
	}
	for(int v : adj[u])
		if(v!=p)
			dfs2(v, u);
}

void dfs3(int u, int p, int v) {
	ans|=(long long)v<<(find(c[s].begin(), c[s].end(), u)-c[s].begin());
	for(int v : adj[u]) {
		if(v==p||find(c[s].begin(), c[s].end(), v)==c[s].end())
			continue;
		dfs3(v, u, Move(v));
		Move(u);
	}
}

long long Ioi(int n, int m, int a[], int b[], int P, int v, int t) {
	s=P;
	for(int i=0; i<n; ++i)
		p[i]=i;
	while(m--) {
		if(join(a[m], b[m])) {
			adj[a[m]].push_back(b[m]);
			adj[b[m]].push_back(a[m]);
		}
	}
	dfs1();
	dfs2();
	dfs3(s, s, v);
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2696 KB Output is correct
2 Correct 6 ms 3432 KB Output is correct
3 Correct 8 ms 4456 KB Output is correct
4 Correct 6 ms 2928 KB Output is correct
5 Correct 6 ms 3096 KB Output is correct
6 Correct 6 ms 3316 KB Output is correct
7 Correct 7 ms 4420 KB Output is correct
8 Correct 7 ms 4348 KB Output is correct
9 Correct 8 ms 4152 KB Output is correct
10 Correct 6 ms 3184 KB Output is correct
11 Correct 8 ms 3436 KB Output is correct
12 Correct 5 ms 2728 KB Output is correct
13 Correct 8 ms 4340 KB Output is correct
14 Correct 8 ms 4344 KB Output is correct
15 Correct 8 ms 4348 KB Output is correct
16 Correct 7 ms 4212 KB Output is correct
17 Correct 8 ms 4352 KB Output is correct
18 Correct 8 ms 4212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 75376 KB Output is correct
2 Correct 162 ms 75376 KB Output is correct
3 Correct 150 ms 75504 KB Output is correct
4 Correct 136 ms 74812 KB Output is correct
5 Correct 133 ms 75504 KB Output is correct
6 Correct 134 ms 75320 KB Output is correct
7 Correct 143 ms 75380 KB Output is correct
8 Correct 137 ms 75384 KB Output is correct
9 Correct 167 ms 75440 KB Output is correct
10 Correct 215 ms 78940 KB Output is correct
11 Correct 163 ms 78716 KB Output is correct
12 Correct 130 ms 68256 KB Output is correct
13 Correct 133 ms 68168 KB Output is correct
14 Correct 142 ms 71664 KB Output is correct
15 Correct 162 ms 75032 KB Output is correct
16 Correct 163 ms 75116 KB Output is correct
17 Correct 161 ms 74960 KB Output is correct
18 Correct 168 ms 74856 KB Output is correct
19 Correct 165 ms 75064 KB Output is correct
20 Correct 147 ms 75504 KB Output is correct
21 Correct 156 ms 74544 KB Output is correct
22 Correct 160 ms 75316 KB Output is correct
23 Correct 160 ms 75492 KB Output is correct
24 Correct 173 ms 75184 KB Output is correct
25 Correct 153 ms 75504 KB Output is correct
26 Correct 173 ms 75440 KB Output is correct
27 Correct 164 ms 75444 KB Output is correct
28 Correct 170 ms 75492 KB Output is correct
29 Correct 148 ms 68768 KB Output is correct
30 Correct 133 ms 71720 KB Output is correct
31 Correct 6 ms 3184 KB Output is correct
32 Correct 6 ms 3448 KB Output is correct
33 Correct 8 ms 4432 KB Output is correct
34 Correct 6 ms 3184 KB Output is correct
35 Correct 6 ms 2932 KB Output is correct
36 Correct 6 ms 3040 KB Output is correct
37 Correct 6 ms 2680 KB Output is correct
38 Correct 6 ms 2724 KB Output is correct
39 Correct 6 ms 2728 KB Output is correct
40 Correct 6 ms 2872 KB Output is correct
41 Correct 6 ms 2936 KB Output is correct
42 Correct 6 ms 2800 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 6 ms 2928 KB Output is correct
3 Correct 6 ms 2836 KB Output is correct
4 Correct 22 ms 14356 KB Output is correct
5 Correct 20 ms 14172 KB Output is correct
6 Correct 22 ms 14204 KB Output is correct
7 Correct 24 ms 14100 KB Output is correct
8 Correct 23 ms 14176 KB Output is correct
9 Correct 143 ms 75348 KB Output is correct
10 Correct 152 ms 75388 KB Output is correct
11 Correct 141 ms 75420 KB Output is correct
12 Correct 6 ms 2556 KB Output is correct
13 Correct 6 ms 2544 KB Output is correct
14 Correct 5 ms 2552 KB Output is correct
15 Correct 6 ms 2600 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 75524 KB Output is correct
2 Correct 168 ms 75628 KB Output is correct
3 Correct 174 ms 75340 KB Output is correct
4 Correct 166 ms 74800 KB Output is correct
5 Correct 155 ms 75888 KB Output is correct
6 Correct 173 ms 75440 KB Output is correct
7 Correct 144 ms 75392 KB Output is correct
8 Correct 154 ms 75248 KB Output is correct
9 Correct 163 ms 75196 KB Output is correct
10 Correct 151 ms 78128 KB Output is correct
11 Correct 151 ms 78712 KB Output is correct
12 Correct 128 ms 68128 KB Output is correct
13 Correct 123 ms 68260 KB Output is correct
14 Correct 141 ms 71512 KB Output is correct
15 Correct 138 ms 75004 KB Output is correct
16 Correct 163 ms 74992 KB Output is correct
17 Correct 146 ms 74936 KB Output is correct
18 Correct 141 ms 74824 KB Output is correct
19 Correct 142 ms 75092 KB Output is correct
20 Correct 157 ms 75548 KB Output is correct
21 Correct 126 ms 74248 KB Output is correct
22 Correct 131 ms 75312 KB Output is correct
23 Correct 139 ms 75312 KB Output is correct
24 Correct 135 ms 75248 KB Output is correct
25 Correct 155 ms 75492 KB Output is correct
26 Correct 158 ms 75432 KB Output is correct
27 Correct 167 ms 75572 KB Output is correct
28 Correct 168 ms 75184 KB Output is correct
29 Correct 142 ms 68768 KB Output is correct
30 Correct 148 ms 71720 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 75344 KB Output is correct
2 Correct 167 ms 75508 KB Output is correct
3 Correct 166 ms 75504 KB Output is correct
4 Correct 158 ms 75528 KB Output is correct
5 Correct 156 ms 76336 KB Output is correct
6 Correct 161 ms 75248 KB Output is correct
7 Correct 163 ms 75316 KB Output is correct
8 Correct 156 ms 75472 KB Output is correct
9 Correct 163 ms 75524 KB Output is correct
10 Correct 200 ms 78752 KB Output is correct
11 Correct 193 ms 78272 KB Output is correct
12 Correct 150 ms 68384 KB Output is correct
13 Correct 159 ms 68136 KB Output is correct
14 Correct 150 ms 71476 KB Output is correct
15 Correct 158 ms 75064 KB Output is correct
16 Correct 162 ms 75132 KB Output is correct
17 Correct 165 ms 75056 KB Output is correct
18 Correct 170 ms 74988 KB Output is correct
19 Correct 157 ms 74996 KB Output is correct
20 Correct 158 ms 75540 KB Output is correct
21 Correct 155 ms 74424 KB Output is correct
22 Correct 153 ms 75320 KB Output is correct
23 Correct 155 ms 75428 KB Output is correct
24 Correct 166 ms 75428 KB Output is correct
25 Correct 155 ms 75388 KB Output is correct
26 Correct 153 ms 75180 KB Output is correct
27 Correct 155 ms 75576 KB Output is correct
28 Correct 143 ms 75580 KB Output is correct
29 Correct 137 ms 69108 KB Output is correct
30 Correct 147 ms 71920 KB Output is correct
31 Correct 6 ms 3312 KB Output is correct
32 Correct 6 ms 3448 KB Output is correct
33 Correct 8 ms 4340 KB Output is correct
34 Correct 6 ms 3056 KB Output is correct
35 Correct 6 ms 2936 KB Output is correct
36 Correct 7 ms 2808 KB Output is correct
37 Correct 6 ms 2548 KB Output is correct
38 Correct 6 ms 2720 KB Output is correct
39 Correct 5 ms 2672 KB Output is correct
40 Correct 6 ms 2928 KB Output is correct
41 Correct 6 ms 2952 KB Output is correct
42 Correct 6 ms 2684 KB Output is correct