Submission #837797

#	Time	Username	Problem	Language	Result	Execution time	Memory
837797		elkernos	Prize (CEOI22_prize)	C++17	0 / 100	3605 ms	920500 KiB

Main

//Sylwia Sapkowska
#include <bits/stdc++.h>
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
void ckmin(int &a, int b) {a = min(a, b);}
typedef pair<int, int> T;
const int K = 20;
 
struct graph{
	vector<vector<int>>g;
	vector<vector<T>> G;
	vector<vector<int>>up, sum;
	vector<set<int>>children;
	vector<int>depth, deg, par, pre, c, D;
	int n, root, tt = 0;
	vector<T>edges;
 
	graph(int nn){
		n = nn;
		g.resize(n+1);
		deg.resize(n+1);
		pre.resize(n+1);
		D.resize(n+1);
		G.resize(n+1);
		children.resize(n+1);
		par.assign(n+1, -1);
		depth.assign(n+1, 0);
		up.resize(n+1, vector<int>(K));
		sum.resize(n+1, vector<int>(K));
		for (int i = 1; i<=n; i++){
			int p; cin >> p;
			if (p == -1) root = i;
			else {
				par[i] = p;
				g[p].emplace_back(i);
				children[p].insert(i);
			}
		}
		for (int i = 1; i<=n; i++) deg[i] = (int)children[i].size();
		dfs(root, root);
	}
 
	void dfs(int v, int pa){
		pre[v] = ++tt;
		up[v][0] = pa;
		for (int i = 1; i<K; i++) up[v][i] = up[up[v][i-1]][i-1];
		for (auto x: g[v]){
			if (x == pa) continue;
			depth[x] = depth[v]+1;
			dfs(x, v);
		}
	}
 
	int lca(int a, int b, int f = 1){
		if (depth[a] > depth[b]) swap(a, b);
		int s = 0;
		for (int i = K-1; i>=0; i--){
			if (depth[up[b][i]] >= depth[a]){
				s += sum[b][i];
				b = up[b][i];
			}
		}
		if (a == b) return (f == 1 ? a : s);
		for (int i = K-1; i>=0; i--){
			if (up[a][i] != up[b][i]){
				s += sum[a][i] + sum[b][i];
				a = up[a][i];
				b = up[b][i];
			}
		}
		s += sum[b][0] + sum[a][0];
		return f == 1 ? up[a][0] : s;
	}
 
	bool cute(int v){
		return deg[v] == 0 || ((int)children[v].size() == 1);
	}
 
	void remove(int v){
		int p = par[v];
		if (p == -1) return;
		if ((int)deg[v] == 0){ //lisc
			deg[p]--;
			children[p].erase(v);
		} else { //z pionowej sciezki ---> jest tylko jedno dziecko,podlaczyc do rodzica v
			auto x = *children[v].begin();
			children[p].erase(v);
			children[p].insert(x);
			par[x] = p;
		}
	}
 
	void make_vt(vector<int>curr){
		sort(curr.begin(), curr.end(), [&](auto x, auto y){
			return pre[x] < pre[y];
		});
		for (int i = 1; i<(int)curr.size(); i++){
			int a = curr[i];
			int b = lca(curr[i], curr[i-1]);
			debug(b, a);
			G[b].emplace_back(a, (int)edges.size());
			edges.emplace_back(a, b);
		}
		root = curr[0];
		dfs2(root, root);
	}
 
	void dfs2(int v, int pa){
		for (auto [x, i]: G[v]){
			if (x == pa) continue;
			D[x] = D[v] + 1;
			dfs2(x, v);
		}
	}
 
	void redo_up(){
		for (int i = 1; i<K; i++){
			for (int v = 1; v<=n; v++){
				up[v][i] = up[up[v][i-1]][i-1];
				sum[v][i] = sum[v][i-1] + sum[up[v][i-1]][i-1];
			}
		}
		depth = D;
		depth.assign(n+1, 0);
		if (!c.empty()) dfs3(root, root);
	}
 
	void dfs3(int v, int pa){
		for (auto [x, i]: G[v]){
			if (x == pa) continue;
			depth[x] = depth[v] + c[i];
			dfs3(x, v);
		}
	}
};
 
void solve(){
	int n, k, q, t; cin >> n >> k >> q >> t;
	graph g1(n), g2(n);
	vector<bool>active(n+1, 1);
	stack<int>s;
	for (int i = 1; i<=n; i++){
		if (g1.cute(i) && g2.cute(i)){
			s.push(i);
		}
	}
	//wystarczy usuwac same liscie
	for (int rep = 0; rep<n-k; rep++){
		while ((int)s.size() && !active[s.top()]) s.pop();
		assert(!s.empty());
		int v = s.top(); s.pop();
		debug(v);
		active[v] = 0;
		g1.remove(v);
		g2.remove(v);
		for (auto ck: {g1.par[v], g2.par[v]}){
			if (ck != -1 && g1.cute(ck) && g2.cute(ck)) {
				s.push(ck);
			}
		}
	}
	vector<int>curr;
	for (int i = 1; i<=n; i++) if (active[i]) curr.emplace_back(i);
	for (auto u: curr) cout << u << " ";
	cout << "\n";
	g1.make_vt(curr);
	g2.make_vt(curr);
	for (auto [a, b]: g1.edges){
		cout << "? " << a << " " << b << "\n";
	}
	cout << "!\n"; cout.flush();
	assert(0);
	for (auto [a, b]: g1.edges){
		int a1, b1, a2, b2; cin >> a1 >> b1 >> a2 >> b2;
		assert(b1 == 0);
		g1.c.emplace_back(a1);
		int lca = g2.lca(a, b);
		for (int rep = 0; rep < 2; rep++){
			g2.up[a][0] = lca;
			g2.sum[a][0] = a2;
			swap(a2, b2); swap(a, b);
		}
	}
	g1.redo_up();
	g2.redo_up();
	vector<T>que;
	while (t--){
		int a, b; cin >> a >> b;
		que.emplace_back(a, b);
	}
	for (auto [a, b]: que){
		int l = g1.lca(a, b);
		cout << g1.depth[a] + g1.depth[b] - 2 * g1.depth[l] << " " << g2.lca(a, b, 0) << "\n";
	}
}
 
int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	solve();
	
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24