oj.uz

Submission #339389

# Submission time Handle Problem Language Result Execution time Memory
339389 2020-12-25T07:20:03 Z nandonathaniel Amusement Park (JOI17_amusement_park) C++14
100 / 100
 306 ms 34900 KB 
#include "Joi.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN2=10005;
vector<int> adj[MAXN2],tree[MAXN2],urutan;
bool visited[MAXN2];
int warna[MAXN2],par[MAXN2],deg[MAXN2],ya[MAXN2];
bitset<MAXN2> mat[MAXN2];
 
void spanningTreeD(){
	par[0]=-1;
	visited[0]=true;
	queue<int> Q;
	Q.push(0);
	while(!Q.empty()){
		int now=Q.front();
		Q.pop();
		urutan.push_back(now);
		for(auto nxt : adj[now]){
			if(visited[nxt])continue;
			visited[nxt]=true;
			par[nxt]=now;
			mat[now][nxt]=1;
			mat[nxt][now]=1;
			Q.push(nxt);
		}
	}
}
 
void buildTreeD(int now){
	int rt=par[now];
	memset(deg,0,sizeof(deg));
	for(auto isi : tree[rt]){
		for(auto isi2 : tree[rt]){
			if(isi<isi2 && mat[isi][isi2]){
				deg[isi]++;
				deg[isi2]++;
			}
		}
	}
	int ganti;
	for(auto isi : tree[rt]){
		if(isi==rt)continue;
		if(deg[isi]==1){
			ganti=isi;
			break;
		}
	}
	for(auto isi : tree[rt]){
		deg[isi]=0;
		if(isi!=ganti)tree[now].push_back(isi);
	}
	tree[now].push_back(now);
	warna[now]=warna[ganti];
}
 
void Joi(int N, int M, int A[], int B[], long long X,
              int T) {
	for(int i=0;i<M;i++){
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	for(int i=0;i<60;i++){
		if(X & (1LL<<i))ya[i]=1;
	}
	spanningTreeD();
	vector<int> awal;
	for(int i=0;i<60;i++){
		awal.push_back(urutan[i]);
		warna[urutan[i]]=i;
	}
	for(int i=0;i<60;i++)tree[urutan[i]]=awal;
	for(int i=60;i<N;i++)buildTreeD(urutan[i]);
	for(int i=0;i<N;i++){
		MessageBoard(i,ya[warna[i]]);
	}
}
#include "Ioi.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN=10005;
vector<int> adj2[MAXN],tree2[MAXN],urutan2;
bool visited2[MAXN];
int warna2[MAXN],par2[MAXN],deg2[MAXN],jaw[MAXN];
bitset<MAXN> mat2[MAXN];
bool subtree[MAXN];
 
void spanningTreeC(){
	par2[0]=-1;
	visited2[0]=true;
	queue<int> Q;
	Q.push(0);
	while(!Q.empty()){
		int now=Q.front();
		Q.pop();
		urutan2.push_back(now);
		for(auto nxt : adj2[now]){
			if(visited2[nxt])continue;
			visited2[nxt]=true;
			par2[nxt]=now;
			mat2[now][nxt]=1;
			mat2[nxt][now]=1;
			Q.push(nxt);
		}
	}
}
 
void buildTreeC(int now){
	int rt=par2[now];
	memset(deg2,0,sizeof(deg2));
	for(auto isi : tree2[rt]){
		for(auto isi2 : tree2[rt]){
			if(isi<isi2 && mat2[isi][isi2]){
				deg2[isi]++;
				deg2[isi2]++;
			}
		}
	}
	int ganti;
	for(auto isi : tree2[rt]){
		if(isi==rt)continue;
		if(deg2[isi]==1){
			ganti=isi;
			break;
		}
	}
	for(auto isi : tree2[rt]){
		deg2[isi]=0;
		if(isi!=ganti)tree2[now].push_back(isi);
	}
	tree2[now].push_back(now);
	warna2[now]=warna2[ganti];
}
 
void dfs(int now,int stat){
	jaw[warna2[now]]=stat;
	visited2[now]=true;
	for(auto nxt : adj2[now]){
		if(visited2[nxt])continue;
		if(!subtree[nxt])continue;
		if(!mat2[now][nxt])continue;
		dfs(nxt,Move(nxt));
		Move(now);
	}
}
 
long long Ioi(int N, int M, int A[], int B[],
                     int P, int V, int T) {
	for(int i=0;i<M;i++){
		adj2[A[i]].push_back(B[i]);
		adj2[B[i]].push_back(A[i]);
	}
	spanningTreeC();
	vector<int> awal;
	for(int i=0;i<60;i++){
		awal.push_back(urutan2[i]);
		warna2[urutan2[i]]=i;
	}
	for(int i=0;i<60;i++)tree2[urutan2[i]]=awal;
	for(int i=60;i<N;i++)buildTreeC(urutan2[i]);
	for(auto isi : tree2[P])subtree[isi]=true;
	memset(visited2,false,sizeof(visited2));
	dfs(P,V);
	long long ans=0;
	for(int i=0;i<60;i++){
		if(jaw[i])ans+=(1LL<<i);
	}
	return ans;
}

Compilation message

Joi.cpp: In function 'void buildTreeD(int)':
Joi.cpp:51:3: warning: 'ganti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |   if(isi!=ganti)tree[now].push_back(isi);
      |   ^~

Ioi.cpp: In function 'void buildTreeC(int)':
Ioi.cpp:52:3: warning: 'ganti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |   if(isi!=ganti)tree2[now].push_back(isi);
      |   ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2288 KB Output is correct
2 Correct 4 ms 2500 KB Output is correct
3 Correct 8 ms 2800 KB Output is correct
4 Correct 4 ms 2152 KB Output is correct
5 Correct 4 ms 2184 KB Output is correct
6 Correct 4 ms 2280 KB Output is correct
7 Correct 8 ms 2952 KB Output is correct
8 Correct 8 ms 3052 KB Output is correct
9 Correct 7 ms 2672 KB Output is correct
10 Correct 4 ms 2408 KB Output is correct
11 Correct 7 ms 2628 KB Output is correct
12 Correct 2 ms 2024 KB Output is correct
13 Correct 8 ms 2800 KB Output is correct
14 Correct 8 ms 3036 KB Output is correct
15 Correct 8 ms 3040 KB Output is correct
16 Correct 8 ms 2800 KB Output is correct
17 Correct 8 ms 2800 KB Output is correct
18 Correct 8 ms 3096 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 34748 KB Output is correct
2 Correct 276 ms 34772 KB Output is correct
3 Correct 271 ms 34564 KB Output is correct
4 Correct 267 ms 34020 KB Output is correct
5 Correct 300 ms 33644 KB Output is correct
6 Correct 296 ms 33564 KB Output is correct
7 Correct 277 ms 33564 KB Output is correct
8 Correct 287 ms 34044 KB Output is correct
9 Correct 276 ms 33692 KB Output is correct
10 Correct 236 ms 33800 KB Output is correct
11 Correct 237 ms 33568 KB Output is correct
12 Correct 246 ms 31140 KB Output is correct
13 Correct 239 ms 30852 KB Output is correct
14 Correct 259 ms 32312 KB Output is correct
15 Correct 271 ms 33564 KB Output is correct
16 Correct 272 ms 33592 KB Output is correct
17 Correct 272 ms 33744 KB Output is correct
18 Correct 283 ms 33608 KB Output is correct
19 Correct 270 ms 33800 KB Output is correct
20 Correct 177 ms 33884 KB Output is correct
21 Correct 170 ms 33216 KB Output is correct
22 Correct 292 ms 34012 KB Output is correct
23 Correct 286 ms 33764 KB Output is correct
24 Correct 290 ms 33564 KB Output is correct
25 Correct 284 ms 33756 KB Output is correct
26 Correct 287 ms 33828 KB Output is correct
27 Correct 288 ms 33756 KB Output is correct
28 Correct 291 ms 33692 KB Output is correct
29 Correct 258 ms 30724 KB Output is correct
30 Correct 272 ms 32272 KB Output is correct
31 Correct 4 ms 2500 KB Output is correct
32 Correct 5 ms 2328 KB Output is correct
33 Correct 7 ms 2928 KB Output is correct
34 Correct 5 ms 2504 KB Output is correct
35 Correct 4 ms 2200 KB Output is correct
36 Correct 2 ms 2232 KB Output is correct
37 Correct 2 ms 2164 KB Output is correct
38 Correct 2 ms 2260 KB Output is correct
39 Correct 2 ms 2024 KB Output is correct
40 Correct 2 ms 2024 KB Output is correct
41 Correct 4 ms 2308 KB Output is correct
42 Correct 2 ms 2296 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2204 KB Output is correct
2 Correct 2 ms 2200 KB Output is correct
3 Correct 2 ms 2200 KB Output is correct
4 Correct 28 ms 7076 KB Output is correct
5 Correct 28 ms 6948 KB Output is correct
6 Correct 28 ms 6948 KB Output is correct
7 Correct 28 ms 7020 KB Output is correct
8 Correct 28 ms 7144 KB Output is correct
9 Correct 170 ms 33472 KB Output is correct
10 Correct 180 ms 33420 KB Output is correct
11 Correct 170 ms 33308 KB Output is correct
12 Correct 2 ms 2256 KB Output is correct
13 Correct 2 ms 2024 KB Output is correct
14 Correct 2 ms 1896 KB Output is correct
15 Correct 2 ms 1896 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 34780 KB Output is correct
2 Correct 272 ms 34780 KB Output is correct
3 Correct 278 ms 34820 KB Output is correct
4 Correct 272 ms 33756 KB Output is correct
5 Correct 299 ms 33820 KB Output is correct
6 Correct 277 ms 33756 KB Output is correct
7 Correct 280 ms 33564 KB Output is correct
8 Correct 283 ms 33880 KB Output is correct
9 Correct 284 ms 33756 KB Output is correct
10 Correct 244 ms 33696 KB Output is correct
11 Correct 250 ms 33816 KB Output is correct
12 Correct 247 ms 31084 KB Output is correct
13 Correct 243 ms 30724 KB Output is correct
14 Correct 257 ms 32016 KB Output is correct
15 Correct 293 ms 34000 KB Output is correct
16 Correct 271 ms 33772 KB Output is correct
17 Correct 272 ms 33692 KB Output is correct
18 Correct 261 ms 33564 KB Output is correct
19 Correct 269 ms 33820 KB Output is correct
20 Correct 172 ms 33764 KB Output is correct
21 Correct 172 ms 33052 KB Output is correct
22 Correct 292 ms 34148 KB Output is correct
23 Correct 302 ms 33692 KB Output is correct
24 Correct 288 ms 33936 KB Output is correct
25 Correct 287 ms 33756 KB Output is correct
26 Correct 285 ms 33564 KB Output is correct
27 Correct 285 ms 33772 KB Output is correct
28 Correct 290 ms 33756 KB Output is correct
29 Correct 261 ms 30724 KB Output is correct
30 Correct 271 ms 32268 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 34672 KB Output is correct
2 Correct 272 ms 34564 KB Output is correct
3 Correct 277 ms 34900 KB Output is correct
4 Correct 268 ms 33752 KB Output is correct
5 Correct 293 ms 33600 KB Output is correct
6 Correct 280 ms 33756 KB Output is correct
7 Correct 290 ms 33796 KB Output is correct
8 Correct 276 ms 33764 KB Output is correct
9 Correct 283 ms 33824 KB Output is correct
10 Correct 240 ms 33716 KB Output is correct
11 Correct 232 ms 33696 KB Output is correct
12 Correct 244 ms 30936 KB Output is correct
13 Correct 244 ms 30980 KB Output is correct
14 Correct 256 ms 32444 KB Output is correct
15 Correct 289 ms 33564 KB Output is correct
16 Correct 273 ms 33780 KB Output is correct
17 Correct 262 ms 33692 KB Output is correct
18 Correct 272 ms 33748 KB Output is correct
19 Correct 262 ms 33564 KB Output is correct
20 Correct 179 ms 33704 KB Output is correct
21 Correct 169 ms 33180 KB Output is correct
22 Correct 292 ms 33756 KB Output is correct
23 Correct 288 ms 33756 KB Output is correct
24 Correct 306 ms 33996 KB Output is correct
25 Correct 286 ms 33764 KB Output is correct
26 Correct 296 ms 33732 KB Output is correct
27 Correct 283 ms 33764 KB Output is correct
28 Correct 281 ms 33760 KB Output is correct
29 Correct 256 ms 31068 KB Output is correct
30 Correct 284 ms 32016 KB Output is correct
31 Correct 4 ms 2500 KB Output is correct
32 Correct 4 ms 2328 KB Output is correct
33 Correct 7 ms 3052 KB Output is correct
34 Correct 4 ms 2664 KB Output is correct
35 Correct 3 ms 2024 KB Output is correct
36 Correct 2 ms 2152 KB Output is correct
37 Correct 2 ms 2024 KB Output is correct
38 Correct 2 ms 2108 KB Output is correct
39 Correct 2 ms 1896 KB Output is correct
40 Correct 3 ms 2212 KB Output is correct
41 Correct 4 ms 2152 KB Output is correct
42 Correct 2 ms 2240 KB Output is correct