Submission #1139798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139798		SmuggingSpun	Amusement Park (JOI17_amusement_park)	C++20	18 / 100	11 ms	4936 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), g(n);
		vector<int>bit(n, -1);
		for(int i = 0; i < m; i++){
			_g[a[i]].emplace_back(b[i]);
			_g[b[i]].emplace_back(a[i]);
		}
		function<void(int)>dfs;
		dfs = [&] (int s){
			bit[s] = -2;
			for(int& d : _g[s]){
				if(bit[d] == -1){
					g[s].emplace_back(d);
					g[d].emplace_back(s);
					dfs(d);
				}
			}
		};
		dfs(0);
		vector<int>T;
		queue<int>q;
		q.push(0);
		for(int i = bit[0] = 0; i < 60; i++){
			int u = q.front();
			q.pop();
			T.emplace_back(u);
			MessageBoard(u, bool(1LL << (bit[u] = i) & x));
			for(int& v : g[u]){
				if(bit[v] == -2){
					q.push(v);
					bit[v] = -1;
				}
			}
		}
		vector<vector<int>>tree(n);
		vector<pair<int, int>>to;
		for(int& i : T){
			tree[i] = T;
			for(int& j : g[i]){
				if(bit[j] < 0){
					to.emplace_back(i, j);
					bit[j] = 0;
				}
			}
		}
		while(!to.empty()){
			auto [u, v] = to.back();
			to.pop_back();
			tree[v] = tree[u];
			for(int& i : tree[u]){
				if(g[i].size() == 1){
					MessageBoard(v, bool(1LL << (bit[v] = bit[i]) & x));
					tree[v].erase(find(tree[v].begin(), tree[v].end(), i));
					tree[v].emplace_back(v);
					break;
				}
			}
			for(int& i : g[v]){
				if(bit[i] < 0){
					to.emplace_back(v, i);
					bit[i] = 0;
				}
			}
		}
	}
}

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 subtask){
	if(subtask == 1){
		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]);
		}
		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(subtask == 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<vector<int>>_g(n), g(n);
	vector<int>bit(n, -1);
	for(int i = 0; i < m; i++){
		_g[a[i]].emplace_back(b[i]);
		_g[b[i]].emplace_back(a[i]);
	}
	function<void(int)>dfs_0;
	dfs_0 = [&] (int s){
		bit[s] = -2;
		for(int& d : _g[s]){
			if(bit[d] == -1){
				g[s].emplace_back(d);
				g[d].emplace_back(s);
				dfs_0(d);
			}
		}
	};
	dfs_0(0);
	vector<int>T;
	queue<int>q;
	q.push(0);
	for(int i = bit[0] = 0; i < 60; i++){
		int u = q.front();
		q.pop();
		bit[u] = T.size();
		T.emplace_back(u);
		for(int& v : g[u]){
			if(bit[v] == -2){
				q.push(v);
				bit[v] = -1;
			}
		}
	}
	vector<vector<int>>tree(n);
	vector<pair<int, int>>to;
	for(int& i : T){
		tree[i] = T;
		for(int& j : g[i]){
			if(bit[j] < 0){
				to.emplace_back(i, j);
				bit[j] = 0;
			}
		}
	}
	while(!to.empty()){
		auto [u, v] = to.back();
		to.pop_back();
		tree[v] = tree[u];
		for(int& i : tree[u]){
			if(g[i].size() == 1){
				tree[v].erase(find(tree[v].begin(), tree[v].end(), i));
				tree[v].emplace_back(v);
				break;
			}
		}
		for(int& i : g[v]){
			if(bit[i] < 0){
				to.emplace_back(v, i);
				bit[i] = 0;
			}
		}
	}
	vector<bool>mark(n, false);
	for(int& i : tree[p]){
		mark[i] = true;
	}
	function<void(int)>dfs_1;
	ll ans = (V == 0 ? 0 : (1LL << bit[p]));
	dfs_1 = [&] (int s){
		mark[s] = false;	
		for(int& d : g[s]){
			if(mark[d]){
				if(Move(d) == 1){
					ans |= 1LL << bit[d];
				}
				dfs_1(d);
				Move(s);
			}
		}
	};
	dfs_1(p);
	return ans;
}

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