Submission #1138896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138896		SmuggingSpun	Amusement Park (JOI17_amusement_park)	C++20	18 / 100	15 ms	2120 KiB

Joi

#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Joi(int n, int m, int a[], int b[], ll x, int T){
	if(T == 1){
		for(int i = 0; i < 60; i++){
			MessageBoard(i, bool(1LL << i & x));
		}
		for(int i = 60; i < n; i++){
			MessageBoard(i, 0);
		}
	}
	else if(T == 3){
		for(int i = 0; i < n; i++){
			MessageBoard(i, bool(1LL << (i % 60) & x));
		}
	}
	else{
		vector<vector<int>>g(n);
		for(int i = 0; i < m; i++){
			g[a[i]].emplace_back(b[i]);
			g[b[i]].emplace_back(a[i]);
		}
		vector<int>id(n, -1);
		int bit = 0;
		function<void(int, int)>dfs;
		dfs = [&] (int s, int p){
			if((id[s] = bit++) == 59){
				bit = 0;
			}
			for(int& d : g[s]){
				if(d != p && id[d] == -1){
					dfs(d, s);
				}
			}
		};
		dfs(0, -1);
		for(int i = 0; i < n; i++){
			MessageBoard(i, bool(1LL << id[i] & x));
		}
	}
}

Ioi

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Ioi(int n, int m, int a[], int b[], int p, int V, int T){
	vector<vector<int>>g(n);
	for(int i = 0; i < m; i++){
		g[a[i]].emplace_back(b[i]);
		g[b[i]].emplace_back(a[i]);
	}
	if(T == 1){
		ll ans = 0;
		vector<int>path, need_path;
		vector<bool>vis(n);
		function<void(int, const int)>dfs;
		dfs = [&] (int s, const int destination){
			path.emplace_back(s);
			if(s == destination){
				need_path = path;	
			}
			vis[s] = true;
			for(int& d : g[s]){
				if(!vis[d]){
					dfs(d, destination);
				}
			}
			path.pop_back();
		};
		for(int i = 0; i < 60; i++){
			fill(vis.begin(), vis.end(), false);
			dfs(p, i);
			for(int j = 1; j < need_path.size(); j++){
				V = Move(p = need_path[j]);
			}
			if(V == 1){
				ans |= 1LL << i;
			}
		}
		return ans;
	}
	else if(T == 3){
		while(p + 1 < n && p % 60 != 59){
			V = Move(++p);
		}
		while(p % 60 != 59){
			V = Move(--p);
		}
		ll ans = (V == 1 ? (1LL << 59) : 0);
		for(int i = 58; i > -1; i--){
			V = Move(--p);
			if(V == 1){
				ans |= 1LL << i;
			}
		}
		return ans;
	}
	vector<int>tour, id(n, -1);
	int cnt_bit = 0;
	function<void(int, int)>dfs;
	dfs = [&] (int s, int p){
		if((id[s] = cnt_bit++) == 59){
			cnt_bit = 0;
		}
		tour.emplace_back(s);
		for(int& d : g[s]){
			if(d != p && id[d] == -1){
				dfs(d, s);
				tour.emplace_back(s);
			}
		}
	};
	dfs(0, -1);
	int pos = 0;
	for(int i = 0; i < tour.size(); i++){
		if(tour[i] == p){
			pos = i;
			break;
		}
	}
	vector<int>bit(60, -1);
	bit[id[p]] = V;
	int cnt_move = 120, init_pos = pos;
	while(++pos < tour.size() && cnt_move > 0){
		bit[id[p = tour[pos]]] = Move(tour[pos]);
		cnt_move--;
	}
	pos--;
	while(--pos >= init_pos && cnt_move > 0){
		Move(p = tour[pos]);
		cnt_move--;
	}
	while(cnt_move > 0){
		bit[id[p = tour[pos--]]] = Move(p);
		cnt_move--;
	}
	ll ans = 0;
	for(int i = 0; i < 60; i++){
		if(bit[i] == 1){
			ans |= 1LL << i;
		}
	}
	return ans;
}

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