Submission #48580

#	Time	Username	Problem	Language	Result	Execution time	Memory
48580		Namnamseo	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	48 ms	24416 KiB

Joi

#include "Joi.h"

#include <bits/stdc++.h>
using namespace std;

static vector<int> edge[10010];
static int ind[10010], nt, hist[20010], dep[10010], par[10010], hn;
static void dfs(int x){
	ind[x] = ++nt;
	hist[hn++] = x;
	for(int y:edge[x]){
		if(ind[y]) continue;
		dep[y]=dep[x]+1;
		par[y]=x;
		dfs(y);
		hist[hn++] = x;
	}
}
static void do_graph(int N, int M, int A[], int B[]){
	for(int i=0; i<M; ++i){
		edge[A[i]].push_back(B[i]);
		edge[B[i]].push_back(A[i]);
	}
	for(int i=0; i<N; ++i) sort(edge[i].begin(), edge[i].end());
	nt = 0; hn = 0;
	dep[0]=1;
	dfs(0);
}

static int pick_bit(long long x, int which){
	return 1 & (x >> which);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	do_graph(N, M, A, B);
	if(*max_element(dep, dep+N) >= 60){
		for(int i = 0; i < N; i++){
			MessageBoard(i, pick_bit(X, (dep[i]-1) % 60));
		}
		return;
	}
	for(int i = 0; i < N; i++){
		MessageBoard(i, pick_bit(X, ind[i] % 60));
	}
}

Ioi

#include "Ioi.h"

#include <bits/stdc++.h>
using namespace std;

static vector<int> edge[10010];
static int ind[10010], nt, hist[20010], dep[10010], par[10010], hn, fh[10010];
static void dfs(int x){
	ind[x] = ++nt;
	fh[x] = hn;
	hist[hn++] = x;
	for(int y:edge[x]){
		if(ind[y]) continue;
		dep[y]=dep[x]+1;
		par[y]=x;
		dfs(y);
		hist[hn++] = x;
	}
}
static void do_graph(int N, int M, int A[], int B[]){
	for(int i=0; i<M; ++i){
		edge[A[i]].push_back(B[i]);
		edge[B[i]].push_back(A[i]);
	}
	for(int i=0; i<N; ++i) sort(edge[i].begin(), edge[i].end());
	nt = 0; hn = 0;
	dep[0]=1;
	dfs(0);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
	do_graph(N, M, A, B);
	if(*max_element(dep, dep+N) >= 60){
		if(dep[P] >= 60){
			long long ret = 0;
			for(int i=0; i<60; ++i){
				if(V) ret |= (1LL << ((dep[P]-1) % 60));
				V = Move(par[P]);
				P = par[P];
			}
			return ret;
		} else {
			while(P != 0){
				V = Move(par[P]);
				P = par[P];
			}
			vector<int> tmp;
			int p = max_element(dep, dep+N) - dep;
			while(true){
				tmp.push_back(p);
				if(p == 0) break;
				p = par[p];
			}
			int n = tmp.size();
			long long ret = 0;
			for(int i=1; i<=60; ++i){
				int p = tmp[n-i];
				if(V) ret |= (1ll << ((dep[p] - 1) % 60));
				if(i < 60){
					V = Move(tmp[n-i-1]);
				}
			}
			return ret;
		}
	}
	int p = fh[P];
	long long mask = 0;
	for(int step=0; step<120; ++step){
		if(p == hn-1) p = 0;
		mask |= (1LL << (ind[hist[p]] % 60));
		++p;
	}
	const long long ALL = ((1LL<<60) - 1);
	if(mask == ALL){
		long long ret = 0, mask = 0;
		int p = fh[P];
		for(int step=0; step<120 || T!=5; ++step){
			if(p == hn-1) p = 0;
			mask |= (1LL << (ind[hist[p]] % 60));
			if(V) ret |= (1LL << (ind[hist[p]] % 60));
			if(mask == ALL) break;
			V = Move(hist[++p]);
		}
		return ret;
	}
	long long ret = 0; mask = 0;
	p = 0;
	for(int i=0; i<hn; ++i) if(hist[i]==P) p=i;
	for(int step=0; step<120 || T!=5; ++step){
		if(p == 0) p = hn-1;
		mask |= (1LL << (ind[hist[p]] % 60));
		if(V) ret |= (1LL << (ind[hist[p]] % 60));
		if(mask == ALL) break;
		V = Move(hist[--p]);
	}
	return ret;
}

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