oj.uz

Submission #246237

# Submission time Handle Problem Language Result Execution time Memory
246237 2020-07-08T12:22:47 Z kshitij_sodani Amusement Park (JOI17_amusement_park) C++14
100 / 100
 224 ms 12216 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#include "Joi.h"
int par[10001];
int find(int no){
	if(par[no]==no){
		return no;
	}
	no=find(par[no]);
	return no;
}
vector<int> adj2[10001];
int par5[10001];
long long xx;
long long co=0;
vector<int> le;
vector<int> pp;
void dfs3(int no,int par2=-1){
	par5[no]=par2;
	for(auto j:adj2[no]){
		if(j==par2){
			continue;
		}
		dfs3(j,no);
	}

}
vector<int> adj3[10001];

void dfs4(int no){
	pp.pb(no);
	for(auto j:adj2[no]){
		if(j==par5[no]){
			continue;
		}
		if(pp.size()<60){
			dfs4(j);
			adj3[no].pb(j);
			adj3[j].pb(no);
		}
		else{
			le.pb(j);
		}
	}
}
vector<int> mm;
int col[10001];
vector<int> comp[10001];
void dfs5(int no,int last=-1){
	mm.pb(no);
	for(auto j:adj3[no]){
		if(j==last){
			continue;
		}
		if(mm.size()<60-pp.size()){
			dfs5(j,no);
		}
	}
}

void Joi(int n, int m, int A[], int B[], long long X, int T) {
	xx=X;
	for(int i=0;i<n;i++){
		par[i]=i;
	}
	for(int i=0;i<m;i++){
		int x=find(A[i]);
		int y=find(B[i]);
		if(x!=y){
			par[x]=y;
			adj2[A[i]].pb(B[i]);
			adj2[B[i]].pb(A[i]);
		}
	}
	dfs3(0);
	le.pb(0);
	while(le.size()){
		int x=le.back();
		le.pop_back();
		pp.clear();
		dfs4(x);
		if(pp.size()==60){
			int j=0;
			for(auto i:pp){
				col[i]=j;
				comp[i]=pp;
				j+=1;
			}
		}
		else{
			mm.clear();
			dfs5(par5[x]);
			int vis[60];
			for(int i=0;i<60;i++){
				vis[i]=0;
			}
			int ind=0;
			for(auto j:pp){
				comp[j]=pp;
			}
			for(auto j:mm){
				vis[col[j]]=1;
				for(auto kk:pp){
					comp[kk].pb(j);
				}
			}
			for(auto j:pp){
				while(vis[ind]){
					ind++;
				}
				col[j]=ind;
				ind++;
			}
		}
	}	
	/*for(int i=0;i<n;i++){
		cout<<col[i]<<":";
		for(auto j:comp[i]){
			cout<<j<<",";
		}
		cout<<endl;
	}
*/
	for(int i=0;i<n;i++){
		if((X&((llo)((llo)1<<col[i])))){
			MessageBoard(i,1);
		}
		else{
			MessageBoard(i,0);
		}
	}
}

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#include "Joi.h"
int par7[10001];
int find9(int no){
	if(par7[no]==no){
		return no;
	}
	no=find9(par7[no]);
	return no;
}
vector<int> adj4[10001];
int par55[10001];
vector<int> le2;
vector<int> pe;
void dfs6(int no,int par2=-1){
	par55[no]=par2;
	for(auto j:adj4[no]){
		if(j==par2){
			continue;
		}
		dfs6(j,no);
	}

}
vector<int> adj5[10001];

void dfs7(int no){
	pe.pb(no);
	for(auto j:adj4[no]){
		if(j==par55[no]){
			continue;
		}
		if(pe.size()<60){
			dfs7(j);
			adj5[no].pb(j);
			adj5[j].pb(no);
		}
		else{
			le2.pb(j);
		}
	}
}
vector<int> mm2;
int col2[10001];
vector<int> comp2[10001];
vector<int> adj11[10001];

void dfs8(int no,int last=-1){
	mm2.pb(no);
	for(auto j:adj5[no]){
		if(j==last){
			continue;
		}
		if(mm2.size()<60-pe.size()){
			dfs8(j,no);
		}
	}
}

long long fin=0;
void dfs12(int no,int last=-1){
	for(auto j:adj11[no]){
		if(j==last){
			continue;
		}
		fin+=(Move(j))*((llo)1<<col2[j]);
		dfs12(j,no);
		Move(no);
	}
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
	for(int i=0;i<n;i++){
		par7[i]=i;
	}
	for(int i=0;i<m;i++){
		int x=find9(A[i]);
		int y=find9(B[i]);
		if(x!=y){
			par7[x]=y;
			adj4[A[i]].pb(B[i]);
			adj4[B[i]].pb(A[i]);
		}
	}
	dfs6(0);
	le2.pb(0);
	while(le2.size()){
		int x=le2.back();
		le2.pop_back();
		pe.clear();
		dfs7(x);
		if(pe.size()==60){
			int j=0;
			for(auto i:pe){
				col2[i]=j;
				comp2[i]=pe;
				j+=1;
			}
		}
		else{
			mm2.clear();
			dfs8(par55[x]);
			int vis[60];
			for(int i=0;i<60;i++){
				vis[i]=0;
			}
			int ind=0;
			for(auto j:pe){
				comp2[j]=pe;
			}
			for(auto j:mm2){
				vis[col2[j]]=1;
				for(auto kk:pe){
					comp2[kk].pb(j);
				}
			}
			for(auto j:pe){
				while(vis[ind]){
					ind++;
				}
				col2[j]=ind;
				ind++;
			}
		}
	}	
	set<int> kot;
	for(auto j:comp2[P]){
		kot.insert(j);
	}
	for(auto j:comp2[P]){
		if(kot.find(par55[j])!=kot.end()){
			adj11[j].pb(par55[j]);
			adj11[par55[j]].pb(j);
		}
	}

	
	if(V){
		fin+=((llo)1<<col2[P]);
	}
	dfs12(P);


	return fin;
}

/*
g++ -std=c++14 -O2 -o aa grader.cpp Joi.cpp Ioi.cpp
*/
/*

7 6 0 5 1
0 1
1 2
0 3
3 4
3 5
0 6





*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2448 KB Output is correct
2 Correct 11 ms 2660 KB Output is correct
3 Correct 11 ms 2852 KB Output is correct
4 Correct 10 ms 2692 KB Output is correct
5 Correct 10 ms 2828 KB Output is correct
6 Correct 11 ms 2704 KB Output is correct
7 Correct 10 ms 2736 KB Output is correct
8 Correct 12 ms 2728 KB Output is correct
9 Correct 12 ms 2744 KB Output is correct
10 Correct 10 ms 2796 KB Output is correct
11 Correct 15 ms 3004 KB Output is correct
12 Correct 10 ms 2440 KB Output is correct
13 Correct 10 ms 2728 KB Output is correct
14 Correct 10 ms 2756 KB Output is correct
15 Correct 10 ms 2724 KB Output is correct
16 Correct 11 ms 2960 KB Output is correct
17 Correct 11 ms 2720 KB Output is correct
18 Correct 10 ms 2704 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 11424 KB Output is correct
2 Correct 192 ms 11392 KB Output is correct
3 Correct 208 ms 11124 KB Output is correct
4 Correct 43 ms 11000 KB Output is correct
5 Correct 36 ms 10204 KB Output is correct
6 Correct 46 ms 10316 KB Output is correct
7 Correct 41 ms 10444 KB Output is correct
8 Correct 42 ms 10636 KB Output is correct
9 Correct 42 ms 10404 KB Output is correct
10 Correct 202 ms 10024 KB Output is correct
11 Correct 224 ms 10136 KB Output is correct
12 Correct 33 ms 9380 KB Output is correct
13 Correct 35 ms 9384 KB Output is correct
14 Correct 34 ms 9760 KB Output is correct
15 Correct 52 ms 12076 KB Output is correct
16 Correct 55 ms 12208 KB Output is correct
17 Correct 43 ms 11188 KB Output is correct
18 Correct 50 ms 11212 KB Output is correct
19 Correct 50 ms 11568 KB Output is correct
20 Correct 30 ms 10412 KB Output is correct
21 Correct 31 ms 10284 KB Output is correct
22 Correct 41 ms 10240 KB Output is correct
23 Correct 43 ms 10412 KB Output is correct
24 Correct 45 ms 10156 KB Output is correct
25 Correct 44 ms 10436 KB Output is correct
26 Correct 50 ms 10392 KB Output is correct
27 Correct 51 ms 10376 KB Output is correct
28 Correct 45 ms 10380 KB Output is correct
29 Correct 40 ms 9680 KB Output is correct
30 Correct 41 ms 9968 KB Output is correct
31 Correct 10 ms 2772 KB Output is correct
32 Correct 10 ms 2776 KB Output is correct
33 Correct 12 ms 2764 KB Output is correct
34 Correct 11 ms 2648 KB Output is correct
35 Correct 10 ms 2676 KB Output is correct
36 Correct 10 ms 2676 KB Output is correct
37 Correct 10 ms 2440 KB Output is correct
38 Correct 10 ms 2692 KB Output is correct
39 Correct 10 ms 2440 KB Output is correct
40 Correct 10 ms 2684 KB Output is correct
41 Correct 10 ms 2704 KB Output is correct
42 Correct 10 ms 2444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2444 KB Output is correct
2 Correct 10 ms 2676 KB Output is correct
3 Correct 10 ms 2688 KB Output is correct
4 Correct 12 ms 3776 KB Output is correct
5 Correct 13 ms 4016 KB Output is correct
6 Correct 13 ms 4004 KB Output is correct
7 Correct 12 ms 3768 KB Output is correct
8 Correct 14 ms 4132 KB Output is correct
9 Correct 27 ms 10660 KB Output is correct
10 Correct 28 ms 10668 KB Output is correct
11 Correct 28 ms 10700 KB Output is correct
12 Correct 10 ms 2464 KB Output is correct
13 Correct 10 ms 2452 KB Output is correct
14 Correct 10 ms 2436 KB Output is correct
15 Correct 10 ms 2584 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 11292 KB Output is correct
2 Correct 196 ms 11432 KB Output is correct
3 Correct 201 ms 12072 KB Output is correct
4 Correct 45 ms 11052 KB Output is correct
5 Correct 35 ms 10732 KB Output is correct
6 Correct 41 ms 10752 KB Output is correct
7 Correct 43 ms 10800 KB Output is correct
8 Correct 41 ms 10872 KB Output is correct
9 Correct 42 ms 10612 KB Output is correct
10 Correct 219 ms 10112 KB Output is correct
11 Correct 210 ms 10128 KB Output is correct
12 Correct 33 ms 9384 KB Output is correct
13 Correct 41 ms 9352 KB Output is correct
14 Correct 37 ms 9908 KB Output is correct
15 Correct 53 ms 12156 KB Output is correct
16 Correct 54 ms 12176 KB Output is correct
17 Correct 45 ms 11180 KB Output is correct
18 Correct 46 ms 11308 KB Output is correct
19 Correct 44 ms 11308 KB Output is correct
20 Correct 27 ms 10472 KB Output is correct
21 Correct 27 ms 10392 KB Output is correct
22 Correct 43 ms 10156 KB Output is correct
23 Correct 41 ms 10172 KB Output is correct
24 Correct 45 ms 10036 KB Output is correct
25 Correct 41 ms 10268 KB Output is correct
26 Correct 41 ms 10152 KB Output is correct
27 Correct 44 ms 10284 KB Output is correct
28 Correct 41 ms 10184 KB Output is correct
29 Correct 40 ms 9600 KB Output is correct
30 Correct 41 ms 9808 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 11404 KB Output is correct
2 Correct 188 ms 11472 KB Output is correct
3 Correct 198 ms 12216 KB Output is correct
4 Correct 44 ms 11288 KB Output is correct
5 Correct 36 ms 11016 KB Output is correct
6 Correct 45 ms 10704 KB Output is correct
7 Correct 43 ms 10732 KB Output is correct
8 Correct 52 ms 11168 KB Output is correct
9 Correct 43 ms 10764 KB Output is correct
10 Correct 213 ms 10100 KB Output is correct
11 Correct 222 ms 10040 KB Output is correct
12 Correct 40 ms 9604 KB Output is correct
13 Correct 34 ms 9388 KB Output is correct
14 Correct 33 ms 9776 KB Output is correct
15 Correct 63 ms 12136 KB Output is correct
16 Correct 55 ms 12196 KB Output is correct
17 Correct 44 ms 11408 KB Output is correct
18 Correct 46 ms 11400 KB Output is correct
19 Correct 49 ms 11420 KB Output is correct
20 Correct 27 ms 10556 KB Output is correct
21 Correct 34 ms 10372 KB Output is correct
22 Correct 53 ms 10188 KB Output is correct
23 Correct 45 ms 10216 KB Output is correct
24 Correct 44 ms 10216 KB Output is correct
25 Correct 45 ms 10176 KB Output is correct
26 Correct 45 ms 10064 KB Output is correct
27 Correct 45 ms 10388 KB Output is correct
28 Correct 43 ms 10172 KB Output is correct
29 Correct 39 ms 9656 KB Output is correct
30 Correct 40 ms 9912 KB Output is correct
31 Correct 10 ms 2784 KB Output is correct
32 Correct 10 ms 2696 KB Output is correct
33 Correct 12 ms 2736 KB Output is correct
34 Correct 10 ms 2804 KB Output is correct
35 Correct 10 ms 2692 KB Output is correct
36 Correct 10 ms 2440 KB Output is correct
37 Correct 10 ms 2688 KB Output is correct
38 Correct 10 ms 2456 KB Output is correct
39 Correct 10 ms 2460 KB Output is correct
40 Correct 10 ms 2568 KB Output is correct
41 Correct 10 ms 2688 KB Output is correct
42 Correct 10 ms 2452 KB Output is correct