Submission #942090

#	Time	Username	Problem	Language	Result	Execution time	Memory
942090		qin	Amusement Park (JOI17_amusement_park)	C++17	83 / 100	22 ms	10484 KiB

Joi

#include <bits/stdc++.h>
#include "Joi.h"
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend();
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1, S = 60;
#ifdef LOCAL
int Move(int x){ return x; }
void MessageBoard(int a, int b){}
#endif
struct graph{
		vv<vv<int>> bg, g;
		vv<int> vis, good, is_top, sz, depth;
		vv<ll> info;
		void init(int n){
				bg.resize(n+1), g.resize(n+1), vis.resize(n+1), good.resize(n+1, 0), info.resize(n+1, 0), sz.resize(n+1), is_top.resize(n+1), depth.resize(n+1);
		}
		void add_edge_b(int a, int b){ bg[a].emplace_back(b), bg[b].emplace_back(a); }
		void add_edge(int a, int b){ g[a].emplace_back(b), g[b].emplace_back(a); }
		void get_tree(int x){
				vis[x] = 1;
				for(int &u : bg[x]) if(!vis[u]) add_edge(x, u), get_tree(u);
		}
		int bit = 0;
		ll process(int x, int gr, ll X, int par){ // X -1 = zwroc, w przeciwnym wypadku zakoduj TRZEBA PAMIETAC, BY POSORTOWAC WEKTOR SASIEDZTWA
				if(is_top[x]) bit = 0;
				ll ret = 0;
				//~ printf("%d: %lld %d\n", x, info[x], bit);
				if(X == -1) ret = info[x]<<bit;
				else info[x] = ((X&(1ll<<bit)) == 0) ? 0 : 1, depth[x] = 1;
				for(int &u : g[x]) if(good[u] == gr && u != par) ++bit, ret += process(u, gr, X, x), depth[x] = max(depth[x], depth[u]+1);
				return ret;
		}
		int l = 0; // ktora grupa
		void get_groups(int x, int par, ll X){
				//~ printf("%d\n", x);
				sz[x] = 1;
				for(int &u : g[x]) if(u != par) get_groups(u, x, X), sz[x] += sz[u];
				if(sz[x] >= 60){
						int cnt = 0, v, p;
						good[x] = ++l, is_top[x] = 1;
						queue<pii> q; q.emplace(x, par);
						while(!q.empty() && cnt < 60){
								v = q.front().fi, p = q.front().se; q.pop(), ++cnt, good[v] = l;
								for(int &u : g[v]) if(u != p && !good[u]) q.emplace(u, v);
						}
						if(X != -1) process(x, good[x], X, 0);
						q = queue<pii>(), sz[x] = 0;
				}
		}
} g;
bool comp(int a, int b){ return g.depth[a] < g.depth[b]; }
void Joi(int n, int m, int a[], int b[], ll X, int T){
		g.init(n+1);
		for(int i = 0; i < m; ++i) g.add_edge_b(a[i]+1, b[i]+1);
		g.get_tree(34);
		for(int i = 1; i <= n; ++i) sort(all(g.g[i]), comp);
		g.get_groups(34, 0, X);
		for(int i = 1; i <= n; ++i) MessageBoard(i-1, g.info[i]);
}
#ifdef LOCAL
void answer(){
	
}
int main(){
		int T = 1;
		for(++T; --T; ) answer();
		return 0;
}
#endif

Ioi

#include <bits/stdc++.h>
#include "Ioi.h"
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend();
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#ifdef LOCAL
int Move(int x){ return x; }
void MessageBoard(int a, int b){}
#endif
struct gph{
		vv<vv<int>> bg, g;
		vv<int> vis, good, is_top, sz, depth;
		vv<ll> info;
		void init(int n){
				bg.resize(n+1), g.resize(n+1), vis.resize(n+1), good.resize(n+1, 0), info.resize(n+1, 0), sz.resize(n+1), is_top.resize(n+1), depth.resize(n+1);
		}
		void add_edge_b(int a, int b){ bg[a].emplace_back(b), bg[b].emplace_back(a); }
		void add_edge(int a, int b){ g[a].emplace_back(b), g[b].emplace_back(a); }
		void get_tree(int x){
				vis[x] = 1;
				for(int &u : bg[x]) if(!vis[u]) add_edge(x, u), get_tree(u);
		}
		vv<int> find_closest_group(int x){ // zwroci wektor tych, po ktorych musze sie poruszac, by dojsc do najblizszej grupy
				fill(all(vis), 0);
				int v;
				vv<int> ret;
				queue<int> q; q.emplace(x); vis[x] = -1;
				while(!q.empty()){
						v = q.front(); q.pop();
						if(good[v]){
								while(vis[v] != -1) ret.emplace_back(v), v = vis[v];
								break;
						}
						for(int &u : bg[v]) if(!vis[u]) vis[u] = v, q.emplace(u);
				}
				q = queue<int>();
				return ret;
		}
		int bit = 0;
		int get_info(int x, int gr, int par, int val){
				int ret = is_top[x] ? x : 0;
				info[x] = val, ++bit;
				for(int &u : g[x]) if(u != par && good[u] == gr) ret = max(ret, get_info(u, gr, x, Move(u-1)));
				if(par && bit < 60) Move(par-1);
				return ret;
		}
		ll process(int x, int gr, ll X, int par){ // X -1 = zwroc, w przeciwnym wypadku zakoduj TRZEBA PAMIETAC, BY POSORTOWAC WEKTOR SASIEDZTWA
				if(is_top[x]) bit = 0;
				ll ret = 0;
				//~ printf("%d: %lld %d\n", x, info[x], bit);
				if(X == -1) ret = info[x]<<bit;
				else info[x] = ((X&(1ll<<bit)) == 0) ? 0 : 1, depth[x] = 1;
				for(int &u : g[x]) if(good[u] == gr && u != par) ++bit, ret += process(u, gr, X, x), depth[x] = max(depth[x], depth[u]+1);
				return ret;
		}
		int l = 0; // ktora grupa
		void get_groups(int x, int par, ll X){
				//~ printf("%d\n", x);
				sz[x] = 1;
				for(int &u : g[x]) if(u != par) get_groups(u, x, X), sz[x] += sz[u];
				if(sz[x] >= 60){
						int cnt = 0, v, p;
						good[x] = ++l, is_top[x] = 1;
						queue<pii> q; q.emplace(x, par);
						while(!q.empty() && cnt < 60){
								v = q.front().fi, p = q.front().se; q.pop(), ++cnt, good[v] = l;
								for(int &u : g[v]) if(u != p && !good[u]) q.emplace(u, v);
						}
						if(X != -1) process(x, good[x], X, 0);
						q = queue<pii>(), sz[x] = 0;
				}
		}
} g;
bool comp(int a, int b){ return g.depth[a] < g.depth[b]; }
ll Ioi(int n, int m, int a[], int b[], int p, int val, int T){
		g.init(n+1); ++p;
		for(int i = 0; i < m; ++i) g.add_edge_b(a[i]+1, b[i]+1);
		g.get_tree(34);
		for(int i = 1; i <= n; ++i) sort(all(g.g[i]), comp);
		g.get_groups(34, 0, -1);
		vv<int> path = g.find_closest_group(p);
		while(!path.empty()) p = path.back(), path.pop_back(), val = Move(p-1);
		g.bit = 0; int TOP = g.get_info(p, g.good[p], 0, val);
		ll ret = g.process(TOP, g.good[TOP], -1, 0);
		//~ printf("%lld\n", ret);
		return ret;
		return 0;
}
#ifdef LOCAL
void answer(){
	
}
int main(){
		int T = 1;
		for(++T; --T; ) answer();
		return 0;
}
#endif

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