Submission #197808

#	Time	Username	Problem	Language	Result	Execution time	Memory
197808		TAISA_	Amusement Park (JOI17_amusement_park)	C++14	80 / 100	86 ms	5072 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
static vector<vector<int>> G;
static vector<int> vis,dep,et;
static int md;
static void dfs(int i){
	vis[i]=1;
	md=max(md,dep[i]);
	et.push_back(i);
	for(auto &e:G[i]){
		if(vis[e]){
			continue;
		}
		dep[e]=dep[i]+1;
		dfs(e);
	}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	G.resize(N);
	vis.resize(N);
	dep.resize(N);
	for(int i=0;i<M;i++){
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	dfs(0);
	if(md>=59){
		for(int i=0;i<N;i++){
			dep[i]%=60;
			MessageBoard(i,((X>>dep[i])&1));
		}
	}else{
		for(int i=0;i<N;i++){
			if(i<60){
				MessageBoard(et[i],((X>>i)&1));
			}else{
				MessageBoard(et[i],0);
			}
		}
	}
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
static vector<vector<int>> G,g;
static vector<int> vis,dep,et,md,par,res;
static int dfs(int i){
	vis[i]=1;
	md[i]=dep[i];
	et.push_back(i);
	for(auto &e:G[i]){
		if(vis[e]){
			continue;
		}
		g[i].push_back(e);
		dep[e]=dep[i]+1;
		par[e]=i;
		md[i]=max(md[i],dfs(e));
	}
	return md[i];
}
static int cnt;
static void dfs2(int i){
	vis[i]=1;
	cnt++;
	if(cnt==60){
		return;
	}
	for(auto &e:G[i]){
		if(vis[e]){
			continue;
		}
		res[e]=Move(e);
		dfs2(e);
		if(cnt==60){
			return;
		}
	}
	if(i>0){
		Move(par[i]);
	}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	G.resize(N);
	g.resize(N);
	vis.resize(N);
	dep.resize(N);
	md.resize(N);
	for(int i=0;i<M;i++){
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	par.resize(N,-1);
	res.resize(N,-1);
	dfs(0);
	ll ans=0;
	res[P]=V;
	if(md[0]>=59){
		while(dep[P]%60>0){
			res[par[P]]=Move(par[P]);
			P=par[P];
		}
		vector<int> vs;
		if(md[P]-dep[P]<59){
			while(md[P]-dep[P]<59||dep[P]%60>0){
				res[par[P]]=Move(par[P]);
				vs.push_back(res[par[P]]);
				P=par[P];
			}
			reverse(vs.begin(),vs.end());
		}else{
			int r=P;
			while(P==r||dep[P]%60>0){
				vs.push_back(res[P]);
				if(g[P].empty()){
					break;
				}
				for(auto &e:g[P]){
					if(md[e]-dep[r]>=59){
						res[e]=Move(e);
						P=e;
						break;
					}
				}
			}
		}
		for(int i=0;i<60;i++){
			if(vs[i]){
				ans+=(1LL<<i);
			}
		}		
	}else{
		while(P>0){
			res[par[P]]=Move(par[P]);
			P=par[P];
		}
		vis.assign(N,0);
		cnt=0;
		dfs2(0);
		for(int i=0;i<60;i++){
			if(res[et[i]]){
				ans+=(1LL<<i);
			}
		}
	}
	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 52 / 55
• Subtask 5: 0 / 17