oj.uz

Submission #51400

# Submission time Handle Problem Language Result Execution time Memory
51400 2018-06-17T23:27:42 Z spencercompton Amusement Park (JOI17_amusement_park) C++17
100 / 100
 45 ms 15496 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// X = message, T = subtask
//At place i, write 0

int n, m;
vector<int> ea;
vector<int> eb;
vector<int> lab;
vector<bool> isgold;
vector<int> gold;
vector<int> fli;
vector<int> adj[10000];
vector<int> order[60];
int point = 0;

void dfs1(int now, int from){
	if(point<60){
		gold.push_back(now);
		lab[now] = point++;
		isgold[now] = true;
	}
	for(int i = 0; i<adj[now].size() && point<60; i++){
		int to = adj[now][i];
		if(to==from){
			continue;
		}
		dfs1(to,now);
	}
}
void dfs2(int now, int from){
	fli[now] = from;
	for(int i = 0; i<adj[now].size(); i++){
		int to = adj[now][i];
		if(to==from){
			continue;
		}
		dfs2(to,now);
	}
}
void dfs3(int now, int from, int level, int val){
	lab[now] = order[val][level];
	for(int i = 0; i<adj[now].size(); i++){
		int to = adj[now][i];
		if(to==from){
			continue;
		}
		dfs3(to,now,(level+1)%60,val);
	}
}
void init(){
	vector<int> comp[n];
	int id[n];
	int sz[n];
	for(int i = 0; i<n; i++){
		comp[i].push_back(i);
		id[i] = i;
		sz[i] = 1;
	}
	for(int i = 0; i<m; i++){
		int ca = id[ea[i]];
		int cb = id[eb[i]];
		if(ca==cb){
			continue;
		}
		if(sz[ca]>sz[cb]){
			swap(ca,cb);
		}
		//ca into cb
		for(int i = 0; i<comp[ca].size(); i++){
			comp[cb].push_back(comp[ca][i]);
			sz[cb]++;
			id[comp[ca][i]] = cb;
		}
		comp[ca].clear();
		adj[ea[i]].push_back(eb[i]);
		adj[eb[i]].push_back(ea[i]);
	}
	lab.resize(n);
	for(int i = 0; i<n; i++){
		lab[i] = -1;
	}
	isgold.resize(n);
	fli.resize(n);
	dfs1(0,-1);
	dfs2(0,-1);
	for(int i = 0; i<60; i++){
		int deg[60];
		for(int j = 0; j<60; j++){
			deg[j] = 0;
		}
		for(int j = 0; j<60; j++){
			for(int k = 0; k<adj[gold[j]].size(); k++){
				int to = adj[gold[j]][k];
				if(isgold[to]){
					deg[j]++;
				}
			}
			if(j!=i && deg[j]==1){
				order[i].push_back(j);
			}
		}
		for(int j = 0; j<order[i].size(); j++){
			int now = gold[order[i][j]];
			for(int k = 0; k<adj[now].size(); k++){
				int to = adj[now][k];
				if(isgold[to]){
					to = lab[to];
					deg[to]--;
					if(deg[to]==1 && to!=i){
						order[i].push_back(to);
					}
				}
			}
		}
		order[i].push_back(i);
		assert(order[i].size()==60);
		int now = gold[i];
		for(int j = 0; j<adj[now].size(); j++){
			int to = adj[now][j];
			if(!isgold[to]){
				dfs3(to,now,0,i);
			}
		}
	}
	for(int i = 0; i<n; i++){
		assert(lab[i]!=-1);
	}
}


void Joi(int N, int M, int A[], int B[], long long X, int T) {
	bool on[60];
	for(int i = 0; i<60; i++){
		if((X&(1LL<<i))!=0){
			on[i] = true;
		}
		else{
			on[i] = false;
		}
	}
	n = N;
	m = M;
	for(int i = 0; i<m; i++){
		ea.push_back(A[i]);
		eb.push_back(B[i]);
	}
	init();
	for(int i = 0; i<n; i++){
		if(on[lab[i]]){
			MessageBoard(i,1);
		}
		else{
			MessageBoard(i,0);
		}
	}
	// cout << "GOT MY JOB DONE" << endl;
}


#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, M;
vector<int> EA;
vector<int> EB;
vector<int> LAB;
vector<bool> ISGOLD;
vector<int> GOLD;
vector<int> FLI;
vector<int> ADJ[10000];
vector<int> ORDER[60];
int POINT = 0;

void DFS1(int now, int from){
	if(POINT<60){
		GOLD.push_back(now);
		LAB[now] = POINT++;
		ISGOLD[now] = true;
	}
	for(int i = 0; i<ADJ[now].size() && POINT<60; i++){
		int to = ADJ[now][i];
		if(to==from){
			continue;
		}
		DFS1(to,now);
	}
}
void DFS2(int now, int from){
	FLI[now] = from;
	for(int i = 0; i<ADJ[now].size(); i++){
		int to = ADJ[now][i];
		if(to==from){
			continue;
		}
		DFS2(to,now);
	}
}
void DFS3(int now, int from, int level, int val){
	LAB[now] = ORDER[val][level];
	for(int i = 0; i<ADJ[now].size(); i++){
		int to = ADJ[now][i];
		if(to==from){
			continue;
		}
		DFS3(to,now,(level+1)%60,val);
	}
}
void INIT(){
	vector<int> comp[N];
	int id[N];
	int sz[N];
	for(int i = 0; i<N; i++){
		comp[i].push_back(i);
		id[i] = i;
		sz[i] = 1;
	}
	for(int i = 0; i<M; i++){
		int ca = id[EA[i]];
		int cb = id[EB[i]];
		if(ca==cb){
			continue;
		}
		if(sz[ca]>sz[cb]){
			swap(ca,cb);
		}
		//ca into cb
		for(int i = 0; i<comp[ca].size(); i++){
			comp[cb].push_back(comp[ca][i]);
			sz[cb]++;
			id[comp[ca][i]] = cb;
		}
		comp[ca].clear();
		ADJ[EA[i]].push_back(EB[i]);
		ADJ[EB[i]].push_back(EA[i]);
	}
	LAB.resize(N);
	for(int i = 0; i<N; i++){
		LAB[i] = -1;
	}
	ISGOLD.resize(N);
	FLI.resize(N);
	for(int i =0 ; i<N; i++){
		FLI[i] = -1;
	}
	DFS1(0,-1);
	DFS2(0,-1);
	for(int i = 0; i<60; i++){
		int deg[60];
		for(int j = 0; j<60; j++){
			deg[j] = 0;
		}
		for(int j = 0; j<60; j++){
			for(int k = 0; k<ADJ[GOLD[j]].size(); k++){
				int to = ADJ[GOLD[j]][k];
				if(ISGOLD[to]){
					deg[j]++;
				}
			}
			if(j!=i && deg[j]==1){
				ORDER[i].push_back(j);
			}
		}
		for(int j = 0; j<ORDER[i].size(); j++){
			int now = GOLD[ORDER[i][j]];
			for(int k = 0; k<ADJ[now].size(); k++){
				int to = ADJ[now][k];
				if(ISGOLD[to]){
					to = LAB[to];
					deg[to]--;
					if(deg[to]==1 && to!=i){
						ORDER[i].push_back(to);
					}
				}
			}
		}
		ORDER[i].push_back(i);
		assert(ORDER[i].size()==60);
		int now = GOLD[i];
		for(int j = 0; j<ADJ[now].size(); j++){
			int to = ADJ[now][j];
			if(!ISGOLD[to]){
				DFS3(to,now,0,i);
			}
		}
	}
}
int know[60];
int numKnow = 0;
void dfs3(int now, int from, int cv){
	if(know[LAB[now]]==-1){
		know[LAB[now]] = cv;
		numKnow++;
	}
	if(ISGOLD[now]){
		for(int i = 0; i<ADJ[now].size() && numKnow<60; i++){
			int to = ADJ[now][i];
			if(!ISGOLD[to]){
				continue;
			}
			if(know[LAB[to]]==-1){
				dfs3(to,now,Move(to));
			}
		}
		if(numKnow<60){
			if(from==-1){
				assert(false);
			}
			Move(from);
		}
	}
	else{
		if(numKnow<60){
			assert(FLI[now]!=-1);
			dfs3(FLI[now],-1,Move(FLI[now]));
		}
	}
}

//P = INITial attraction, V = value there, T = sub
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
	N = n;
	M = m;
	for(int i = 0; i<m; i++){
		EA.push_back(A[i]);
		EB.push_back(B[i]);
	}
	for(int i = 0; i<60; i++){
		know[i] = -1;
	}
	INIT();
	dfs3(P,-1,V);
	ll ret = 0LL;
	assert(numKnow==60);
	for(int i = 0; i<60; i++){
		if(know[i]==1){
			ret += (1LL<<i);
		}
	}
	return ret;
}

Compilation message

Joi.cpp: In function 'void dfs1(int, int)':
Joi.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size() && point<60; i++){
                 ~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs2(int, int)':
Joi.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs3(int, int, int, int)':
Joi.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'void init()':
Joi.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<comp[ca].size(); i++){
                  ~^~~~~~~~~~~~~~~~
Joi.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = 0; k<adj[gold[j]].size(); k++){
                   ~^~~~~~~~~~~~~~~~~~~~
Joi.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<order[i].size(); j++){
                  ~^~~~~~~~~~~~~~~~
Joi.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = 0; k<adj[now].size(); k++){
                   ~^~~~~~~~~~~~~~~~
Joi.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<adj[now].size(); j++){
                  ~^~~~~~~~~~~~~~~~

Ioi.cpp: In function 'void DFS1(int, int)':
Ioi.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<ADJ[now].size() && POINT<60; i++){
                 ~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void DFS2(int, int)':
Ioi.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<ADJ[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void DFS3(int, int, int, int)':
Ioi.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<ADJ[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void INIT()':
Ioi.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<comp[ca].size(); i++){
                  ~^~~~~~~~~~~~~~~~
Ioi.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = 0; k<ADJ[GOLD[j]].size(); k++){
                   ~^~~~~~~~~~~~~~~~~~~~
Ioi.cpp:106:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<ORDER[i].size(); j++){
                  ~^~~~~~~~~~~~~~~~
Ioi.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = 0; k<ADJ[now].size(); k++){
                   ~^~~~~~~~~~~~~~~~
Ioi.cpp:122:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<ADJ[now].size(); j++){
                  ~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs3(int, int, int)':
Ioi.cpp:138:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<ADJ[now].size() && numKnow<60; i++){
                  ~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1120 KB Output is correct
2 Correct 4 ms 1336 KB Output is correct
3 Correct 4 ms 1400 KB Output is correct
4 Correct 4 ms 1608 KB Output is correct
5 Correct 4 ms 1752 KB Output is correct
6 Correct 4 ms 2044 KB Output is correct
7 Correct 6 ms 2224 KB Output is correct
8 Correct 5 ms 2224 KB Output is correct
9 Correct 4 ms 2224 KB Output is correct
10 Correct 4 ms 2224 KB Output is correct
11 Correct 8 ms 2288 KB Output is correct
12 Correct 4 ms 2288 KB Output is correct
13 Correct 5 ms 2288 KB Output is correct
14 Correct 4 ms 2288 KB Output is correct
15 Correct 5 ms 2288 KB Output is correct
16 Correct 4 ms 2288 KB Output is correct
17 Correct 4 ms 2288 KB Output is correct
18 Correct 4 ms 2288 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5828 KB Output is correct
2 Correct 35 ms 5896 KB Output is correct
3 Correct 35 ms 5896 KB Output is correct
4 Correct 32 ms 5896 KB Output is correct
5 Correct 27 ms 6028 KB Output is correct
6 Correct 28 ms 6160 KB Output is correct
7 Correct 27 ms 6160 KB Output is correct
8 Correct 26 ms 6160 KB Output is correct
9 Correct 27 ms 6160 KB Output is correct
10 Correct 25 ms 6160 KB Output is correct
11 Correct 25 ms 6160 KB Output is correct
12 Correct 23 ms 6160 KB Output is correct
13 Correct 23 ms 6160 KB Output is correct
14 Correct 26 ms 6160 KB Output is correct
15 Correct 25 ms 6160 KB Output is correct
16 Correct 25 ms 6160 KB Output is correct
17 Correct 27 ms 6160 KB Output is correct
18 Correct 26 ms 6160 KB Output is correct
19 Correct 26 ms 6160 KB Output is correct
20 Correct 20 ms 6160 KB Output is correct
21 Correct 19 ms 6160 KB Output is correct
22 Correct 27 ms 6160 KB Output is correct
23 Correct 27 ms 6160 KB Output is correct
24 Correct 27 ms 6160 KB Output is correct
25 Correct 27 ms 6160 KB Output is correct
26 Correct 27 ms 6160 KB Output is correct
27 Correct 25 ms 6160 KB Output is correct
28 Correct 27 ms 6160 KB Output is correct
29 Correct 25 ms 6160 KB Output is correct
30 Correct 33 ms 6160 KB Output is correct
31 Correct 5 ms 6160 KB Output is correct
32 Correct 4 ms 6160 KB Output is correct
33 Correct 4 ms 6160 KB Output is correct
34 Correct 4 ms 6160 KB Output is correct
35 Correct 5 ms 6160 KB Output is correct
36 Correct 4 ms 6160 KB Output is correct
37 Correct 4 ms 6160 KB Output is correct
38 Correct 4 ms 6160 KB Output is correct
39 Correct 4 ms 6160 KB Output is correct
40 Correct 5 ms 6160 KB Output is correct
41 Correct 5 ms 6160 KB Output is correct
42 Correct 5 ms 6160 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6160 KB Output is correct
2 Correct 4 ms 6160 KB Output is correct
3 Correct 4 ms 6160 KB Output is correct
4 Correct 6 ms 6160 KB Output is correct
5 Correct 6 ms 6160 KB Output is correct
6 Correct 6 ms 6160 KB Output is correct
7 Correct 6 ms 6160 KB Output is correct
8 Correct 7 ms 6160 KB Output is correct
9 Correct 19 ms 6160 KB Output is correct
10 Correct 19 ms 6160 KB Output is correct
11 Correct 20 ms 6328 KB Output is correct
12 Correct 4 ms 6384 KB Output is correct
13 Correct 4 ms 6384 KB Output is correct
14 Correct 5 ms 6384 KB Output is correct
15 Correct 5 ms 6384 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6384 KB Output is correct
2 Correct 35 ms 6384 KB Output is correct
3 Correct 34 ms 6384 KB Output is correct
4 Correct 25 ms 6384 KB Output is correct
5 Correct 32 ms 6396 KB Output is correct
6 Correct 34 ms 6408 KB Output is correct
7 Correct 27 ms 6408 KB Output is correct
8 Correct 27 ms 6408 KB Output is correct
9 Correct 26 ms 6644 KB Output is correct
10 Correct 25 ms 6696 KB Output is correct
11 Correct 25 ms 6696 KB Output is correct
12 Correct 23 ms 6696 KB Output is correct
13 Correct 24 ms 6696 KB Output is correct
14 Correct 25 ms 6716 KB Output is correct
15 Correct 26 ms 7016 KB Output is correct
16 Correct 26 ms 7208 KB Output is correct
17 Correct 26 ms 7524 KB Output is correct
18 Correct 26 ms 7688 KB Output is correct
19 Correct 26 ms 7880 KB Output is correct
20 Correct 19 ms 8552 KB Output is correct
21 Correct 19 ms 8560 KB Output is correct
22 Correct 27 ms 9472 KB Output is correct
23 Correct 26 ms 9596 KB Output is correct
24 Correct 27 ms 9696 KB Output is correct
25 Correct 28 ms 9864 KB Output is correct
26 Correct 27 ms 10024 KB Output is correct
27 Correct 33 ms 10268 KB Output is correct
28 Correct 27 ms 10320 KB Output is correct
29 Correct 25 ms 10320 KB Output is correct
30 Correct 33 ms 10548 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 10712 KB Output is correct
2 Correct 35 ms 10720 KB Output is correct
3 Correct 35 ms 10724 KB Output is correct
4 Correct 40 ms 10728 KB Output is correct
5 Correct 28 ms 11288 KB Output is correct
6 Correct 34 ms 11352 KB Output is correct
7 Correct 27 ms 11352 KB Output is correct
8 Correct 39 ms 11496 KB Output is correct
9 Correct 28 ms 11496 KB Output is correct
10 Correct 32 ms 11496 KB Output is correct
11 Correct 26 ms 11496 KB Output is correct
12 Correct 24 ms 11496 KB Output is correct
13 Correct 25 ms 11504 KB Output is correct
14 Correct 25 ms 11512 KB Output is correct
15 Correct 25 ms 11768 KB Output is correct
16 Correct 27 ms 12168 KB Output is correct
17 Correct 26 ms 12380 KB Output is correct
18 Correct 26 ms 12692 KB Output is correct
19 Correct 25 ms 12796 KB Output is correct
20 Correct 19 ms 13424 KB Output is correct
21 Correct 19 ms 13536 KB Output is correct
22 Correct 27 ms 13796 KB Output is correct
23 Correct 27 ms 13992 KB Output is correct
24 Correct 27 ms 14400 KB Output is correct
25 Correct 27 ms 14728 KB Output is correct
26 Correct 27 ms 14864 KB Output is correct
27 Correct 26 ms 15028 KB Output is correct
28 Correct 27 ms 15464 KB Output is correct
29 Correct 28 ms 15496 KB Output is correct
30 Correct 26 ms 15496 KB Output is correct
31 Correct 5 ms 15496 KB Output is correct
32 Correct 4 ms 15496 KB Output is correct
33 Correct 4 ms 15496 KB Output is correct
34 Correct 5 ms 15496 KB Output is correct
35 Correct 4 ms 15496 KB Output is correct
36 Correct 4 ms 15496 KB Output is correct
37 Correct 4 ms 15496 KB Output is correct
38 Correct 4 ms 15496 KB Output is correct
39 Correct 4 ms 15496 KB Output is correct
40 Correct 4 ms 15496 KB Output is correct
41 Correct 4 ms 15496 KB Output is correct
42 Correct 4 ms 15496 KB Output is correct