Submission #51400

#	Time	Username	Problem	Language	Result	Execution time	Memory
51400		spencercompton	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	45 ms	15496 KiB

Joi

#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;
}

Ioi

#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 (stderr)

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 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17