Submission #926521

#	Time	Username	Problem	Language	Result	Execution time	Memory
926521		daoquanglinh2007	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	18 ms	5084 KiB

Joi

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

#define ll long long

const int NM = 1e4;

namespace _Joi{
	vector <int> g[NM+5], son[NM+5];
	int parent[NM+5], dep[NM+5];
	bool vis[NM+5], in_max_path[NM+5];
	int MAX_DEP = 0, cnt = 0;
	
	void dfs(int u, int p){
		parent[u] = p;
		if (p != -1) son[p].push_back(u);
		dep[u] = (p == -1 ? 0 : dep[p]+1);
		MAX_DEP = max(MAX_DEP, dep[u]);
		vis[u] = 1;
		for (int v : g[u]){
			if (vis[v]) continue;
			dfs(v, u);
		}
	}
	void build(int u, ll X){
		cnt++;
		MessageBoard(u, (X>>(cnt-1))&1);
		vis[u] = 1;
		for (int v : son[u]){
			if (!in_max_path[v]) continue;
			build(v, X);
		}
		for (int v : son[u]){
			if (in_max_path[v]) continue;
			if (cnt < 60) build(v, X);
		}
	}
	void solve(int N, int M, int A[], int B[], ll X, int T){
		assert(T >= 1 && T <= 5);
		for (int i = 0; i < M; i++){
			g[A[i]].push_back(B[i]);
			g[B[i]].push_back(A[i]);
		}
		dfs(0, -1);
		if (MAX_DEP >= 60){
			for (int i = 0; i < N; i++)
				MessageBoard(i, (X>>(dep[i]%60))&1);
			return;
		}
		bool found = 0;
		for (int i = 0; i < N; i++)
			if (dep[i] == MAX_DEP && !found){
				found = 1;
				for (int j = i; j != -1; j = parent[j]){
					in_max_path[j] = 1;
				}
			}
		for (int i = 0; i < N; i++) vis[i] = 0;
		build(0, X);
		for (int i = 0; i < N; i++)
			if (!vis[i]) MessageBoard(i, 0);
	}
}

void Joi(int N, int M, int A[], int B[], ll X, int T){
	_Joi::solve(N, M, A, B, X, T);
}

Ioi

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

#define ll long long

const int NM = 1e4;

namespace _Ioi{
	vector <int> g[NM+5], son[NM+5];
	int parent[NM+5], dep[NM+5];
	bool vis[NM+5], in_max_path[NM+5];
	int MAX_DEP = 0, cnt = 0;
	int L[NM+5], f[NM+5];
	ll X = 0;
	
	void dfs(int u, int p){
		parent[u] = p;
		if (p != -1) son[p].push_back(u);
		dep[u] = (p == -1 ? 0 : dep[p]+1);
		MAX_DEP = max(MAX_DEP, dep[u]);
		vis[u] = 1;
		for (int v : g[u]){
			if (vis[v]) continue;
			dfs(v, u);
		}
	}
	void build(int u){
		cnt++;
		L[u] = cnt-1;
		for (int v : son[u]){
			if (!in_max_path[v]) continue;
			build(v);
		}
		for (int v : son[u]){
			if (in_max_path[v]) continue;
			if (cnt < 60) build(v);
		}
	}
	void calc(int u){
		f[u] = dep[u];
		for (int v : son[u]){
			calc(v);
			f[u] = max(f[u], f[v]);
		}
	}
	void get_ans(int u, int val){
		if (val) X += (1LL<<L[u]);
		for (int v : son[u]){
			if (L[v] == -1) continue;
			if (in_max_path[v]) continue;
			get_ans(v, Move(v));
			Move(u);
		}
		for (int v : son[u]){
			if (L[v] == -1) continue;
			if (!in_max_path[v]) continue;
			get_ans(v, Move(v));
		}
	}
	ll solve(int N, int M, int A[], int B[], int P, int V, int T){
		assert(T >= 1 && T <= 5);
		for (int i = 0; i < M; i++){
			g[A[i]].push_back(B[i]);
			g[B[i]].push_back(A[i]);
		}
		dfs(0, -1);
		if (MAX_DEP >= 60){
			if (dep[P] >= 60){
				if (V) X += (1LL<<(dep[P]%60));
				for (int i = 1; i < 60; i++){
					P = parent[P];
					V = Move(P);
					if (V) X += (1LL<<(dep[P]%60));
				}
			}
			else{
				while (P > 0){
					P = parent[P];
					V = Move(P);
				}
				calc(0);
				if (V) X++;
				for (int i = 1; i < 60; i++){
					for (int nxt : son[P]){
						if (f[nxt] < 59) continue;
						P = nxt;
						V = Move(nxt);
						if (V) X += (1LL<<i);
						break;
					}
				}
			}
			return X;
		}
		bool found = 0;
		for (int i = 0; i < N; i++)
			if (dep[i] == MAX_DEP && !found){
				found = 1;
				for (int j = i; j != -1; j = parent[j]){
					in_max_path[j] = 1;
				}
			}
		for (int i = 0; i < N; i++) L[i] = -1;
		build(0);
		while (P > 0){
			P = parent[P];
			V = Move(P);
		}
		get_ans(0, V);
		return X;
	}
}

ll Ioi(int N, int M, int A[], int B[], int P, int V, int T){
	return _Ioi::solve(N, M, A, B, P, V, T);
}

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