oj.uz

Submission #294165

# Submission time Handle Problem Language Result Execution time Memory
294165 2020-09-08T16:11:37 Z patrikpavic2 Amusement Park (JOI17_amusement_park) C++17
100 / 100
 37 ms 10756 KB 
#include "Joi.h"
#include <vector>
#include <algorithm>
#include <cstdio>


#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 1e5 + 500;

int dep[N], ppar[N], tr[N], mks[N], par[N];
int tko[N], bit[N], cur = 0;
vector < int > v[N];


int pr(int x){
	if(x == ppar[x]) return x;
	return ppar[x] = pr(ppar[x]);
}

bool cmp(int x, int y){
	return mks[x] > mks[y];
}

int dfs(int x, int lst){
	mks[x] = dep[x]; par[x] = lst;
	vector < int > vv;
	for(int y : v[x]){
		if(y == lst) continue;
		vv.PB(y);
		dep[y] = dep[x] + 1;
		dfs(y, x);
		mks[x] = max(mks[x], mks[y]);
	}
	sort(vv.begin(), vv.end(), cmp);
	v[x] = vv;
	return mks[x];
}

void dfs2(int x){
	if(cur == 60) return;
	tko[x] = cur++; bit[x] = 1;
	//printf("tko[ %d ] = %d bit[ %d ] = %d\n", x, tko[x], x, bit[x]);
	for(int y : v[x])
		dfs2(y);
}

void Joi(int n, int m, int A[], int B[], long long X, int T) {
	for(int i = 0;i < n;i++)
		ppar[i] = i;
	for(int i = 0;i < m;i++){
		if(pr(A[i]) == pr(B[i]))
			continue;
		ppar[pr(A[i])] = pr(B[i]);
		v[A[i]].PB(B[i]);
		v[B[i]].PB(A[i]);
		tr[i] = 1;
	}
	dfs(0, 0);
	if(mks[0] >= 59){
		//printf("Slucaj 1\n");
		for(int i = 0;i < n;i++)
			MessageBoard(i, !!(X & (1LL << (dep[i] % 60))));
		return;
	}
	//printf("Slucaj 2\n");
	dfs2(0);
	for(int i = 0;i < n;i++)
		MessageBoard(i, !!(X & (1LL << tko[i])));
	
}
#include "Ioi.h"
#include <vector>
#include <algorithm>
#include <cstdio>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 1e5 + 500;

int dep2[N], ppar22[N], tr2[N], mks2[N], par2[N];
int tko2[N], bit2[N], cur2 = 0;
ll ans = 0;
vector < int > v2[N];

int pr2(int x){
	if(x == ppar22[x]) return x;
	return ppar22[x] = pr2(ppar22[x]);
}

bool cmp2(int x, int y){
	return mks2[x] > mks2[y];
}

int dfs2(int x, int lst){
	mks2[x] = dep2[x]; par2[x] = lst;
	vector < int > v2v2;
	for(int y : v2[x]){
		if(y == lst) continue;
		v2v2.PB(y);
		dep2[y] = dep2[x] + 1;
		dfs2(y, x);
		mks2[x] = max(mks2[x], mks2[y]);
	}
	sort(v2v2.begin(), v2v2.end(), cmp2);
	v2[x] = v2v2;
	return mks2[x];
}

void dfs22(int x){
	if(cur2 == 60) return;
	tko2[x] = cur2++; bit2[x] = 1;
	for(int y : v2[x])
		dfs22(y);
}

int odg2 = -1;

void odg2ov2or(int x, bool nazad){
	ans += (1LL << tko2[x]) * odg2;
	reverse(v2[x].begin(), v2[x].end()); 
	for(int y : v2[x]){
		if(bit2[y]){
			odg2 = Move(y);
			odg2ov2or(y, nazad || (y != v2[x].back()));
			if(y != v2[x].back() || nazad){
				odg2 = Move(x);
			}
		}
	}
	reverse(v2[x].begin(), v2[x].end()); 
}

long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
	for(int i = 0;i < n;i++)
		ppar22[i] = i;
	for(int i = 0;i < m;i++){
		if(pr2(A[i]) == pr2(B[i]))
			continue;
		ppar22[pr2(A[i])] = pr2(B[i]);
		v2[A[i]].PB(B[i]);
		v2[B[i]].PB(A[i]);
		tr2[i] = 1;
	}
	dfs2(0, 0);
	if(mks2[0] >= 59){
		int lst = V;
		//printf("P = %d mks2[ %d ] = %d\n", P, P, mks2[P]);
		while(mks2[P] - dep2[P] < 59){
			lst = Move(par2[P]);
			P = par2[P];
		}
		for(int i = 0;i < 60;i++){
			ans += (1LL << (dep2[P] % 60)) * lst;
			if(i < 59){
				lst = Move(v2[P][0]);
				P = v2[P][0];
			}
		}
		return ans;
	}
	dfs22(0);
	odg2 = V;
	while(P != 0){
		odg2 = Move(par2[P]);
		P = par2[P];
	}
	odg2ov2or(0, 0);
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5548 KB Output is correct
2 Correct 4 ms 5544 KB Output is correct
3 Correct 4 ms 5660 KB Output is correct
4 Correct 4 ms 5512 KB Output is correct
5 Correct 4 ms 5536 KB Output is correct
6 Correct 4 ms 5512 KB Output is correct
7 Correct 4 ms 5656 KB Output is correct
8 Correct 4 ms 5648 KB Output is correct
9 Correct 4 ms 5664 KB Output is correct
10 Correct 4 ms 5512 KB Output is correct
11 Correct 7 ms 5844 KB Output is correct
12 Correct 4 ms 5544 KB Output is correct
13 Correct 4 ms 5648 KB Output is correct
14 Correct 4 ms 5648 KB Output is correct
15 Correct 4 ms 5520 KB Output is correct
16 Correct 5 ms 5652 KB Output is correct
17 Correct 5 ms 5668 KB Output is correct
18 Correct 4 ms 5656 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8372 KB Output is correct
2 Correct 33 ms 8376 KB Output is correct
3 Correct 33 ms 8356 KB Output is correct
4 Correct 22 ms 7976 KB Output is correct
5 Correct 24 ms 8876 KB Output is correct
6 Correct 23 ms 8620 KB Output is correct
7 Correct 22 ms 8828 KB Output is correct
8 Correct 22 ms 8748 KB Output is correct
9 Correct 24 ms 8964 KB Output is correct
10 Correct 20 ms 7984 KB Output is correct
11 Correct 19 ms 7984 KB Output is correct
12 Correct 19 ms 7572 KB Output is correct
13 Correct 19 ms 7444 KB Output is correct
14 Correct 20 ms 7640 KB Output is correct
15 Correct 20 ms 7852 KB Output is correct
16 Correct 22 ms 7848 KB Output is correct
17 Correct 23 ms 7724 KB Output is correct
18 Correct 22 ms 8112 KB Output is correct
19 Correct 22 ms 7724 KB Output is correct
20 Correct 19 ms 9132 KB Output is correct
21 Correct 19 ms 9004 KB Output is correct
22 Correct 23 ms 8364 KB Output is correct
23 Correct 23 ms 8868 KB Output is correct
24 Correct 23 ms 8388 KB Output is correct
25 Correct 23 ms 8672 KB Output is correct
26 Correct 22 ms 8980 KB Output is correct
27 Correct 23 ms 8988 KB Output is correct
28 Correct 23 ms 8952 KB Output is correct
29 Correct 22 ms 8352 KB Output is correct
30 Correct 24 ms 8720 KB Output is correct
31 Correct 4 ms 5512 KB Output is correct
32 Correct 4 ms 5512 KB Output is correct
33 Correct 4 ms 5648 KB Output is correct
34 Correct 4 ms 5512 KB Output is correct
35 Correct 5 ms 5536 KB Output is correct
36 Correct 4 ms 5512 KB Output is correct
37 Correct 4 ms 5668 KB Output is correct
38 Correct 4 ms 5684 KB Output is correct
39 Correct 4 ms 5544 KB Output is correct
40 Correct 5 ms 5512 KB Output is correct
41 Correct 5 ms 5552 KB Output is correct
42 Correct 5 ms 5552 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5512 KB Output is correct
2 Correct 4 ms 5512 KB Output is correct
3 Correct 4 ms 5512 KB Output is correct
4 Correct 6 ms 6348 KB Output is correct
5 Correct 6 ms 6324 KB Output is correct
6 Correct 6 ms 6324 KB Output is correct
7 Correct 6 ms 6356 KB Output is correct
8 Correct 6 ms 6196 KB Output is correct
9 Correct 19 ms 10748 KB Output is correct
10 Correct 19 ms 10756 KB Output is correct
11 Correct 19 ms 10540 KB Output is correct
12 Correct 4 ms 5548 KB Output is correct
13 Correct 4 ms 5544 KB Output is correct
14 Correct 4 ms 5556 KB Output is correct
15 Correct 4 ms 5512 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8356 KB Output is correct
2 Correct 33 ms 8420 KB Output is correct
3 Correct 32 ms 8356 KB Output is correct
4 Correct 22 ms 7844 KB Output is correct
5 Correct 23 ms 9904 KB Output is correct
6 Correct 23 ms 8876 KB Output is correct
7 Correct 23 ms 8748 KB Output is correct
8 Correct 24 ms 8120 KB Output is correct
9 Correct 23 ms 8364 KB Output is correct
10 Correct 19 ms 8184 KB Output is correct
11 Correct 20 ms 8192 KB Output is correct
12 Correct 20 ms 7828 KB Output is correct
13 Correct 19 ms 7648 KB Output is correct
14 Correct 20 ms 7616 KB Output is correct
15 Correct 23 ms 7788 KB Output is correct
16 Correct 20 ms 7724 KB Output is correct
17 Correct 20 ms 7724 KB Output is correct
18 Correct 23 ms 7724 KB Output is correct
19 Correct 22 ms 7724 KB Output is correct
20 Correct 19 ms 9204 KB Output is correct
21 Correct 19 ms 9228 KB Output is correct
22 Correct 23 ms 8656 KB Output is correct
23 Correct 25 ms 8708 KB Output is correct
24 Correct 23 ms 8848 KB Output is correct
25 Correct 23 ms 8876 KB Output is correct
26 Correct 23 ms 8640 KB Output is correct
27 Correct 23 ms 9216 KB Output is correct
28 Correct 22 ms 8408 KB Output is correct
29 Correct 23 ms 8212 KB Output is correct
30 Correct 23 ms 8544 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8368 KB Output is correct
2 Correct 33 ms 8356 KB Output is correct
3 Correct 34 ms 8556 KB Output is correct
4 Correct 22 ms 7724 KB Output is correct
5 Correct 26 ms 10224 KB Output is correct
6 Correct 22 ms 8236 KB Output is correct
7 Correct 22 ms 8364 KB Output is correct
8 Correct 27 ms 8876 KB Output is correct
9 Correct 22 ms 8692 KB Output is correct
10 Correct 20 ms 7984 KB Output is correct
11 Correct 19 ms 8088 KB Output is correct
12 Correct 19 ms 7572 KB Output is correct
13 Correct 22 ms 7572 KB Output is correct
14 Correct 20 ms 7584 KB Output is correct
15 Correct 20 ms 7844 KB Output is correct
16 Correct 23 ms 7968 KB Output is correct
17 Correct 22 ms 7836 KB Output is correct
18 Correct 20 ms 7740 KB Output is correct
19 Correct 23 ms 7740 KB Output is correct
20 Correct 19 ms 9020 KB Output is correct
21 Correct 19 ms 9148 KB Output is correct
22 Correct 23 ms 8668 KB Output is correct
23 Correct 23 ms 8508 KB Output is correct
24 Correct 22 ms 8616 KB Output is correct
25 Correct 22 ms 8508 KB Output is correct
26 Correct 23 ms 8380 KB Output is correct
27 Correct 23 ms 9020 KB Output is correct
28 Correct 23 ms 9248 KB Output is correct
29 Correct 20 ms 8740 KB Output is correct
30 Correct 23 ms 8496 KB Output is correct
31 Correct 4 ms 5512 KB Output is correct
32 Correct 4 ms 5512 KB Output is correct
33 Correct 4 ms 5664 KB Output is correct
34 Correct 4 ms 5540 KB Output is correct
35 Correct 4 ms 5536 KB Output is correct
36 Correct 4 ms 5512 KB Output is correct
37 Correct 4 ms 5548 KB Output is correct
38 Correct 4 ms 5384 KB Output is correct
39 Correct 4 ms 5556 KB Output is correct
40 Correct 4 ms 5512 KB Output is correct
41 Correct 4 ms 5540 KB Output is correct
42 Correct 4 ms 5540 KB Output is correct