oj.uz

Submission #941781

# Submission time Handle Problem Language Result Execution time Memory
941781 2024-03-09T12:04:14 Z qin Amusement Park (JOI17_amusement_park) C++17
0 / 100
 231 ms 262144 KB 
#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;
		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);
		}
		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] = 0;
				while(!q.empty()){
						v = q.front(); q.pop();
						if(good[v]){
								while(vis[v]) ret.emplace_back(v), v = vis[v];
								break;
						}
						for(int &u : g[v]) if(!vis[u]) vis[u] = x, q.emplace(u);
				}
				q = queue<int>();
				return ret;
		}
		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;
				if(X == -1) ret = info[x]<<bit;
				else info[x] = ((X&(1ll<<bit)) == 0) ? 0 : 1;
				for(int &u : g[x]) if(u != par) ++bit, ret += process(u, gr, X, x);
				return ret;
		}
		queue<pii> q;
		int l = 0; // ktora grupa
		void get_groups(int x, int par, int X){
				sz[x] = 1;
				for(int &u : g[x]) if(u != par) get_groups(u, x, X), sz[x] += sz[u];
				if(sz[x] >= S){
						int cnt = 0, v, p;
						good[x] = ++l, is_top[x] = 1;
						q.emplace(x, par);
						while(!q.empty() && cnt < S){
								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;
				}
		}
};
void Joi(int n, int m, int a[], int b[], ll X, int T){
		graph g; g.init(n+1);
		for(int i = 0; i < m; ++i) g.add_edge_b(a[i]+1, b[i]+1);
		g.get_tree(1);
		for(int i = 1; i <= n; ++i) sort(all(g.g[i]));
		g.get_groups(1, 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

#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;
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;
		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);
		}
		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] = 0;
				while(!q.empty()){
						v = q.front(); q.pop();
						if(good[v]){
								while(vis[v]) ret.emplace_back(v), v = vis[v];
								break;
						}
						for(int &u : g[v]) if(!vis[u]) vis[u] = x, q.emplace(u);
				}
				q = queue<int>();
				return ret;
		}
		int get_info(int x, int gr, int par, int val){
				int ret = is_top[x] ? x : 0;
				info[x] = val;
				for(int &u : g[x]) if(u != par && good[u] == gr) ret = max(ret, get_info(u, gr, x, Move(u)));
				return ret;
		}
		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;
				if(X == -1) ret = info[x]<<bit;
				else info[x] = ((X&(1ll<<bit)) == 0) ? 0 : 1;
				for(int &u : g[x]) if(u != par) ++bit, ret += process(u, gr, X, x);
				return ret;
		}
		queue<pii> q;
		int l = 0; // ktora grupa
		void get_groups(int x, int par, int X){
				sz[x] = 1;
				for(int &u : g[x]) if(u != par) get_groups(u, x, X), sz[x] += sz[u];
				if(sz[x] >= S){
						int cnt = 0, v, p;
						good[x] = ++l, is_top[x] = 1;
						q.emplace(x, par);
						while(!q.empty() && cnt < S){
								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;
				}
		}
};
ll Ioi(int n, int m, int a[], int b[], int p, int val, int T){
		graph g; g.init(n+1);
		for(int i = 0; i < m; ++i) g.add_edge_b(a[i]+1, b[i]+1);
		g.get_tree(1);
		for(int i = 1; i <= n; ++i) sort(all(g.g[i]));
		g.get_groups(1, 0, -1);
		vv<int> path = g.find_closest_group(p);
		while(!path.empty()) p = path.back(), path.pop_back(), val = Move(p);
		int TOP = g.get_info(p, g.good[p], 0, val);
		return g.process(TOP, g.good[TOP], -1, 0);
}
#ifdef LOCAL
void answer(){
	
}
int main(){
		int T = 1;
		for(++T; --T; ) answer();
		return 0;
}
#endif

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 231 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 7012 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 226 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 6920 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 6932 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -