Submission #101005

#	Time	Username	Problem	Language	Result	Execution time	Memory
101005		autumn_eel	Amusement Park (JOI17_amusement_park)	C++14	77 / 100	66 ms	6060 KiB

Joi

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

#include "Joi.h"

vector<int>E[20000];
bool used[20000];
int dep[20000];
int height[20000];
vector<int>vs;

int dfs(int v,int d){
	used[v]=true;
	dep[v]=d;
	vs.push_back(v);
	for(int u:E[v]){
		if(used[u])continue;
		height[v]=max(height[v],dfs(u,d+1)+1);
		vs.push_back(v);
	}
	return height[v];
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	rep(i,M){
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	dfs(0,0);
	if(height[0]<60){
		set<int>se1,se2;
		for(int v:vs){
			if(!se1.count(v)){
				se2.insert(v);
			}
			if(se2.size()==60){
				int cnt=0;
				for(int i:se2){
					MessageBoard(i,X>>cnt&1);
					cnt++;
				}
				for(int i:se2){
					se1.insert(i);
				}
				se2.clear();
			}
		}
		int cnt=0;
		for(int i:se2){
			MessageBoard(i,X>>cnt&1);
			cnt++;
		}
		return;
	}
	rep(i,N){
		dep[i]%=60;
		MessageBoard(i,X>>dep[i]&1);
	}
}

Ioi

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

#include "Ioi.h"

static vector<int>E[20000];
static vector<int>G[20000];
static bool used[20000];
static int dep[20000];
static int height[20000];
static int par[20000];
static vector<int>vs;
static int vid[20000];

static int dfs(int v,int p,int d){
	used[v]=true;
	vid[v]=vs.size();
	vs.push_back(v);
	par[v]=p;
	dep[v]=d;
	for(int u:E[v]){
		if(used[u])continue;
		G[v].push_back(u);
		height[v]=max(height[v],dfs(u,v,d+1)+1);
		vs.push_back(v);
	}
	return height[v];
}

long long Ioi(int N, int M, int A[], int B[], int Pos, int V, int T) {
	rep(i,M){
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	dfs(0,-1,0);
	if(height[0]<60){
		set<int>se1,se2;
		map<int,int>id;
		for(int v:vs){
			if(!se1.count(v)){
				se2.insert(v);
			}
			if(se2.size()==60){
				int cnt=0;
				for(int i:se2){
					id[i]=cnt;
					cnt++;
				}
				for(int i:se2){
					se1.insert(i);
				}
				se2.clear();
			}
		}
		int cnt=0;
		for(int i:se2){
			id[i]=cnt;
			cnt++;
		}
		int x=vid[Pos];
		
		set<int>se;
		int r;
		for(r=x;r<vs.size();r++){
			se.insert(id[vs[r]]);
			if(se.size()==60)break;
		}
		if(r==vs.size())r=vs.size()-1;
		int l;
		for(l=x;l>=0;l--){
			se.insert(id[vs[l]]);
			if(se.size()==60)break;
		}
		if(l==-1)l=0;
		
		set<int>Se;
		int l2;
		for(l2=x;l2>=0;l2--){
			Se.insert(id[vs[l2]]);
			if(Se.size()==60)break;
		}
		if(l2==-1)l2=0;
		int r2;
		for(r2=x;r2<vs.size();r2++){
			Se.insert(id[vs[r2]]);
			if(Se.size()==60)break;
		}
		if(r2==vs.size())r2=vs.size()-1;
		if(r2-l2+min(r2-x,x-l2)<r-l+min(r-x,x-l)){
			swap(l,l2);
			swap(r,r2);
		}
		
		set<int>SE;
		int l3=x,r3=x;
		while(1){
			if(l3>0){
				SE.insert(id[vs[--l3]]);
			}
			if(r3<vs.size()-1){
				SE.insert(id[vs[++r3]]);
			}
			if(SE.size()==60)break;
		}
		
		if(r3-l3+min(r3-x,x-l3)<r-l+min(r-x,x-l)){
			swap(l,l3);
			swap(r,r3);
		}
		
		map<int,vector<int>>MP;
		rep(i,vs.size()){
			MP[id[vs[i]]].push_back(i);
		}
		int l4=x,r4=x;
		rep(i,60){
			int Min=INT_MAX;
			int t=-1;
			auto it=lower_bound(MP[i].begin(),MP[i].end(),x);
			if(it!=MP[i].end()){
				Min=*it-x;
				t=*it;
			}
			if(it!=MP[i].begin()){
				it--;
				if(Min>x-*it){
					Min=x-*it;
					t=*it;
				}
			}
			assert(Min<=900);
			l4=min(l4,*it);
			r4=max(r4,*it);
		}
		if(r4-l4+min(r4-x,x-l4)<r-l+min(r-x,x-l)){
			swap(l,l4);
			swap(r,r4);
		}
		
		ll ans=0;
		ans|=ll(V)<<id[Pos];
		if(abs(x-l)<abs(x-r)){
			//left
			for(int i=x-1;i>=l;i--){
				ans|=ll(Move(vs[i]))<<id[vs[i]];
			}
			for(int i=l+1;i<=r;i++){
				ans|=ll(Move(vs[i]))<<id[vs[i]];
			}
		}
		else{
			//right
			for(int i=x+1;i<=r;i++){
				ans|=ll(Move(vs[i]))<<id[vs[i]];
			}
			for(int i=r-1;i>=l;i--){
				ans|=ll(Move(vs[i]))<<id[vs[i]];
			}
		}
		return ans;
	}
	
	rep(i,N){
		dep[i]%=60;
	}
	
	int pos=Pos;
	
	set<int>se{dep[pos]};
	ll ans=ll(V)<<dep[pos];
	
	while(1){
		if(se.size()==60||pos==0){
			break;
		}
		pos=par[pos];
		ans|=ll(Move(pos))<<dep[pos];
		se.insert(dep[pos]);
	}
	while(1){
		if(se.size()==60)break;
		for(int u:G[pos]){
			if(height[u]+1==height[pos]){
				pos=u;
				ans|=ll(Move(pos))<<dep[pos];
				se.insert(dep[pos]);
				break;
			}
		}
	}
	return ans;
}

Compilation message (stderr)

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:67:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(r=x;r<vs.size();r++){
           ~^~~~~~~~~~
Ioi.cpp:71:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r==vs.size())r=vs.size()-1;
      ~^~~~~~~~~~~
Ioi.cpp:87:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(r2=x;r2<vs.size();r2++){
            ~~^~~~~~~~~~
Ioi.cpp:91:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r2==vs.size())r2=vs.size()-1;
      ~~^~~~~~~~~~~
Ioi.cpp:103:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(r3<vs.size()-1){
       ~~^~~~~~~~~~~~
Ioi.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
Ioi.cpp:115:3: note: in expansion of macro 'rep'
   rep(i,vs.size()){
   ^~~
Ioi.cpp:121:8: warning: variable 't' set but not used [-Wunused-but-set-variable]
    int t=-1;
        ^

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