oj.uz

Submission #298439

# Submission time Handle Problem Language Result Execution time Memory
298439 2020-09-12T21:04:51 Z pit4h Amusement Park (JOI17_amusement_park) C++14
100 / 100
 219 ms 23000 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int _B = 60;
void build_tree(int x, vector<vector<int>>& g, vector<bool>& vis, vector<vector<int>>& G) {
	vis[x] = 1;
	for(int i: g[x]) {
		if(!vis[i]) {
			G[x].push_back(i);
			G[i].push_back(x);
			build_tree(i, g, vis, G);
		}
	}
}
struct Nodes {
	int key, val, par;	
};
void dfs(int x, int p, vector<vector<int>>& g, int& counter, vector<vector<Nodes>>& T, vector<int>& rep) {
	if(counter<_B) {
		T[0].push_back({x, counter, p});	
		rep[x] = 0;
	}
	else {
		rep[x] = T.size();
		T.push_back(T[rep[p]]);
		map<int, bool> has_child;
		for(auto it: T[rep[x]]) {
			has_child[it.par] = 1;
		}
		bool fail=1;
		for(auto &it: T[rep[x]]) {
			if(it.key != p && !has_child[it.key]) {
				it.key = x;
				it.par = p;
				fail = 0;
				break;
			}
		}
		if(fail) { // delete root
			int root;
			for(auto &it: T[rep[x]]) {
				if(it.par == -1) {
					root = it.key;
					it.key = x;
					it.par = p;
				}
			}
			for(auto &it: T[rep[x]]) {
				if(it.par == root) {
					it.par = -1;
				}
			}
		}
	}
	counter++;
	for(int i: g[x]) {
		if(i!=p) {
			dfs(i, x, g, counter, T, rep);
		}
	}
}
void Joi(int N, int M, int A[], int B[], ll X, int T) {
	// MessageBoard();
	vector<vector<int>> g(N), G(N);
	for(int i=0; i<M; ++i) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	vector<bool> vis(N);
	build_tree(0, g, vis, G);
	vector<vector<Nodes>> Tree(1);
	int counter = 0;
	vector<int> rep(N);
	dfs(0, -1, G, counter, Tree, rep);	
	vector<int> value(N);
	for(auto t: Tree) {
		for(auto it: t) {
			value[it.key] = (bool)(X&(1LL<<it.val));
		}
	}
	for(int i=0; i<N; ++i) {
		MessageBoard(i, value[i]);
	}
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int bits = 60;
void _build_tree(int x, vector<vector<int>>& g, vector<bool>& vis, vector<vector<int>>& G) {
	vis[x] = 1;
	for(int i: g[x]) {
		if(!vis[i]) {
			G[x].push_back(i);
			G[i].push_back(x);
			_build_tree(i, g, vis, G);
		}
	}
}
struct _Nodes {
	int key, val, par;	
};
void _dfs(int x, int p, vector<vector<int>>& g, int& counter, vector<vector<_Nodes>>& T, vector<int>& rep) {
	if(counter<bits) {
		T[0].push_back({x, counter, p});	
		rep[x] = 0;
	}
	else {
		rep[x] = T.size();
		T.push_back(T[rep[p]]);
		map<int, bool> has_child;
		for(auto it: T[rep[x]]) {
			has_child[it.par] = 1;
		}
		bool fail=1;
		for(auto &it: T[rep[x]]) {
			if(it.key != p && !has_child[it.key]) {
				it.key = x;
				it.par = p;
				fail = 0;
				break;
			}
		}
		if(fail) { // delete root
			int root;
			for(auto &it: T[rep[x]]) {
				if(it.par == -1) {
					root = it.key;
					it.key = x;
					it.par = p;
				}
			}
			for(auto &it: T[rep[x]]) {
				if(it.par == root) {
					it.par = -1;
				}
			}
		}
	}
	counter++;
	for(int i: g[x]) {
		if(i!=p) {
			_dfs(i, x, g, counter, T, rep);
		}
	}
}
void solve(int x, int prv, int v, vector<vector<int>>& g, vector<bool>& vis, vector<int>& value, ll& X) {
	vis[x] = 1;
	X += (ll)v * (1LL<<value[x]);
	for(int i: g[x]) {
		if(!vis[i]) {
			solve(i, x, Move(i), g, vis, value, X);
		}
	}
	if(prv != -1) {
		Move(prv);
	}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	vector<vector<int>> g(N), G(N);
	for(int i=0; i<M; ++i) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	vector<bool> vis(N);
	_build_tree(0, g, vis, G);
	vector<vector<_Nodes>> Tree(1);
	int counter = 0;
	vector<int> rep(N);
	_dfs(0, -1, G, counter, Tree, rep);
	vis = vector<bool>(N, 1);
	vector<int> value(N);
	for(auto it: Tree[rep[P]]) {
		vis[it.key] = 0;
		value[it.key] = it.val;
	}
	ll X = 0;
	solve(P, -1, V, G, vis, value, X);
	return X;
}

Compilation message

Joi.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&, int&, std::vector<std::vector<Nodes> >&, std::vector<int>&)':
Joi.cpp:50:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     if(it.par == root) {
      |     ^~

Ioi.cpp: In function 'void _dfs(int, int, std::vector<std::vector<int> >&, int&, std::vector<std::vector<_Nodes> >&, std::vector<int>&)':
Ioi.cpp:50:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     if(it.par == root) {
      |     ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 996 KB Output is correct
2 Correct 2 ms 928 KB Output is correct
3 Correct 4 ms 1256 KB Output is correct
4 Correct 2 ms 960 KB Output is correct
5 Correct 2 ms 956 KB Output is correct
6 Correct 2 ms 1040 KB Output is correct
7 Correct 5 ms 1488 KB Output is correct
8 Correct 2 ms 1188 KB Output is correct
9 Correct 4 ms 1040 KB Output is correct
10 Correct 2 ms 940 KB Output is correct
11 Correct 7 ms 1280 KB Output is correct
12 Correct 2 ms 1020 KB Output is correct
13 Correct 4 ms 1180 KB Output is correct
14 Correct 4 ms 1168 KB Output is correct
15 Correct 4 ms 1312 KB Output is correct
16 Correct 4 ms 1188 KB Output is correct
17 Correct 4 ms 1396 KB Output is correct
18 Correct 4 ms 1192 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 21832 KB Output is correct
2 Correct 213 ms 22200 KB Output is correct
3 Correct 207 ms 22244 KB Output is correct
4 Correct 125 ms 18836 KB Output is correct
5 Correct 200 ms 21004 KB Output is correct
6 Correct 188 ms 20128 KB Output is correct
7 Correct 204 ms 20224 KB Output is correct
8 Correct 186 ms 20588 KB Output is correct
9 Correct 181 ms 20372 KB Output is correct
10 Correct 54 ms 18948 KB Output is correct
11 Correct 46 ms 18968 KB Output is correct
12 Correct 109 ms 17148 KB Output is correct
13 Correct 110 ms 17300 KB Output is correct
14 Correct 115 ms 18040 KB Output is correct
15 Correct 150 ms 18580 KB Output is correct
16 Correct 156 ms 18868 KB Output is correct
17 Correct 112 ms 18872 KB Output is correct
18 Correct 114 ms 19220 KB Output is correct
19 Correct 119 ms 18960 KB Output is correct
20 Correct 173 ms 21000 KB Output is correct
21 Correct 172 ms 20640 KB Output is correct
22 Correct 194 ms 19880 KB Output is correct
23 Correct 195 ms 20608 KB Output is correct
24 Correct 196 ms 20040 KB Output is correct
25 Correct 198 ms 20436 KB Output is correct
26 Correct 201 ms 20380 KB Output is correct
27 Correct 199 ms 20724 KB Output is correct
28 Correct 197 ms 20656 KB Output is correct
29 Correct 177 ms 18724 KB Output is correct
30 Correct 186 ms 19368 KB Output is correct
31 Correct 2 ms 932 KB Output is correct
32 Correct 2 ms 904 KB Output is correct
33 Correct 2 ms 1324 KB Output is correct
34 Correct 2 ms 936 KB Output is correct
35 Correct 2 ms 1100 KB Output is correct
36 Correct 2 ms 776 KB Output is correct
37 Correct 2 ms 1000 KB Output is correct
38 Correct 1 ms 1016 KB Output is correct
39 Correct 1 ms 1024 KB Output is correct
40 Correct 2 ms 972 KB Output is correct
41 Correct 2 ms 964 KB Output is correct
42 Correct 2 ms 996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 968 KB Output is correct
2 Correct 3 ms 1084 KB Output is correct
3 Correct 2 ms 960 KB Output is correct
4 Correct 28 ms 4324 KB Output is correct
5 Correct 26 ms 4284 KB Output is correct
6 Correct 26 ms 4292 KB Output is correct
7 Correct 33 ms 4148 KB Output is correct
8 Correct 27 ms 4148 KB Output is correct
9 Correct 163 ms 22924 KB Output is correct
10 Correct 167 ms 23000 KB Output is correct
11 Correct 169 ms 22804 KB Output is correct
12 Correct 1 ms 904 KB Output is correct
13 Correct 2 ms 1064 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 1 ms 904 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 21584 KB Output is correct
2 Correct 211 ms 22224 KB Output is correct
3 Correct 219 ms 22080 KB Output is correct
4 Correct 113 ms 18880 KB Output is correct
5 Correct 203 ms 21956 KB Output is correct
6 Correct 183 ms 20644 KB Output is correct
7 Correct 185 ms 20432 KB Output is correct
8 Correct 209 ms 19828 KB Output is correct
9 Correct 186 ms 20064 KB Output is correct
10 Correct 68 ms 18968 KB Output is correct
11 Correct 54 ms 18868 KB Output is correct
12 Correct 109 ms 17260 KB Output is correct
13 Correct 113 ms 17272 KB Output is correct
14 Correct 112 ms 17800 KB Output is correct
15 Correct 149 ms 18768 KB Output is correct
16 Correct 147 ms 19084 KB Output is correct
17 Correct 109 ms 19128 KB Output is correct
18 Correct 117 ms 18880 KB Output is correct
19 Correct 112 ms 18964 KB Output is correct
20 Correct 176 ms 21252 KB Output is correct
21 Correct 174 ms 20500 KB Output is correct
22 Correct 200 ms 20392 KB Output is correct
23 Correct 198 ms 20448 KB Output is correct
24 Correct 195 ms 20244 KB Output is correct
25 Correct 201 ms 20456 KB Output is correct
26 Correct 206 ms 20488 KB Output is correct
27 Correct 200 ms 20884 KB Output is correct
28 Correct 194 ms 20192 KB Output is correct
29 Correct 178 ms 18560 KB Output is correct
30 Correct 187 ms 19700 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 21740 KB Output is correct
2 Correct 209 ms 22240 KB Output is correct
3 Correct 212 ms 22032 KB Output is correct
4 Correct 115 ms 19000 KB Output is correct
5 Correct 199 ms 22688 KB Output is correct
6 Correct 184 ms 20052 KB Output is correct
7 Correct 188 ms 19984 KB Output is correct
8 Correct 180 ms 20576 KB Output is correct
9 Correct 191 ms 20336 KB Output is correct
10 Correct 52 ms 18964 KB Output is correct
11 Correct 55 ms 18968 KB Output is correct
12 Correct 109 ms 17256 KB Output is correct
13 Correct 111 ms 17260 KB Output is correct
14 Correct 111 ms 17944 KB Output is correct
15 Correct 129 ms 18892 KB Output is correct
16 Correct 148 ms 19160 KB Output is correct
17 Correct 115 ms 18852 KB Output is correct
18 Correct 113 ms 18924 KB Output is correct
19 Correct 131 ms 18856 KB Output is correct
20 Correct 178 ms 21004 KB Output is correct
21 Correct 184 ms 20656 KB Output is correct
22 Correct 197 ms 20260 KB Output is correct
23 Correct 208 ms 20148 KB Output is correct
24 Correct 197 ms 20144 KB Output is correct
25 Correct 196 ms 20344 KB Output is correct
26 Correct 197 ms 19884 KB Output is correct
27 Correct 195 ms 20772 KB Output is correct
28 Correct 201 ms 20928 KB Output is correct
29 Correct 181 ms 19152 KB Output is correct
30 Correct 193 ms 19628 KB Output is correct
31 Correct 3 ms 1160 KB Output is correct
32 Correct 2 ms 1168 KB Output is correct
33 Correct 2 ms 1200 KB Output is correct
34 Correct 2 ms 936 KB Output is correct
35 Correct 2 ms 960 KB Output is correct
36 Correct 2 ms 984 KB Output is correct
37 Correct 2 ms 1004 KB Output is correct
38 Correct 2 ms 904 KB Output is correct
39 Correct 1 ms 1020 KB Output is correct
40 Correct 2 ms 776 KB Output is correct
41 Correct 2 ms 964 KB Output is correct
42 Correct 2 ms 776 KB Output is correct