oj.uz

Submission #1044036

# Submission time Handle Problem Language Result Execution time Memory
1044036 2024-08-05T06:33:38 Z ㅇㅇ(#11061) Prize (CEOI22_prize) C++17
100 / 100
 1645 ms 465100 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using pii=array<int,2>;
const int N=1000005;
int n,k,q,t,m;
int p[2][20][N],r[2],dep[2][N],in[N],out[N],x[N];
vector<int> g[2][N];
vector<pii> qry,G[2][N],ask;
bool vis[2][N];
int dist[2][N];
int lca(int t,int u,int v){
	if(dep[t][u]>dep[t][v]) swap(u,v);
	int d=dep[t][v]-dep[t][u];
	for(int b=0;b<20;b++) if((d>>b)&1) v=p[t][b][v];
	if(u==v) return u;
	for(int b=19;b>=0;b--) if(p[t][b][u]!=p[t][b][v]){
		u=p[t][b][u];
		v=p[t][b][v];
	}
	return p[t][0][u];
}
void dfs0(int t,int u){
	for(int v: g[t][u]){
		dep[t][v]=dep[t][u]+1;
		dfs0(t,v);
	}
}
void dfs1(int u){
	in[u]=++m;
	x[m]=u;
	for(int v: g[0][u]) dfs1(v);
	out[u]=m;
}
int dfs2(int u){
	vector<int> V;
	for(int v: g[1][u]){
		int w=dfs2(v);
		if(w) V.push_back(w);
	}
	if(in[u]>k){
		if(V.size()==0) return 0;
		if(V.size()==1) return V[0];
		int v1=V.back(); V.pop_back();
		for(int v2: V){
			if(in[v1]>in[v2]) swap(v1,v2);
			qry.push_back({v1,v2});
		}
		return v1;
	} else{
		if(V.size()==0) return u;
		int v1=u;
		for(int v2: V){
			if(in[v1]>in[v2]) swap(v1,v2);
			qry.push_back({v1,v2});
		}
		return v1;
	}
}
void dfs3(int t,int u){
	vis[t][u]=1;
	for(auto [v,w]: G[t][u]) if(!vis[t][v]){
		dist[t][v]=dist[t][u]+w;
		dfs3(t,v);
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k>>q>>t;
	for(int t=0;t<2;t++){
		for(int i=1;i<=n;i++){
			cin>>p[t][0][i];
			if(p[t][0][i]==-1) r[t]=i;
			else g[t][p[t][0][i]].push_back(i);
		}
		for(int b=1;b<20;b++) for(int i=1;i<=n;i++) p[t][b][i]=p[t][b-1][p[t][b-1][i]];
		dfs0(t,r[t]);
	}
	dfs1(r[0]);
	for(int i=1;i<=k;i++) cout<<x[i]<<" \n"[i==k];
	cout<<flush;
	dfs2(r[1]);
	for(auto [u,v]: qry) cout<<"? "<<u<<" "<<v<<"\n";
	cout<<"!\n"<<flush;
	for(auto [u,v]: qry){
		int w1=lca(0,u,v),w2=lca(1,u,v);
		int d1u,d1v,d2u,d2v;
		cin>>d1u>>d1v>>d2u>>d2v;
		G[0][w1].push_back({u,d1u});
		G[0][u].push_back({w1,-d1u});
		G[0][w1].push_back({v,d1v});
		G[0][v].push_back({w1,-d1v});
		G[1][w2].push_back({u,d2u});
		G[1][u].push_back({w2,-d2u});
		G[1][w2].push_back({v,d2v});
		G[1][v].push_back({w2,-d2v});
	}
	for(int i=1;i<=n;i++){
		if(G[0][i].size()&&!vis[0][i]) dfs3(0,i);
		if(G[1][i].size()&&!vis[1][i]) dfs3(1,i);
	}
	for(int u,v,i=1;i<=t;i++){
		cin>>u>>v;
		ask.push_back({u,v});
	}
	for(auto [u,v]: ask){
		int w1=lca(0,u,v),w2=lca(1,u,v);
		cout<<(dist[0][u]+dist[0][v]-2*dist[0][w1])<<" "<<(dist[1][u]+dist[1][v]-2*dist[1][w2])<<"\n";
	}
	cout<<flush;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 369700 KB Output is correct
2 Correct 835 ms 372704 KB Output is correct
3 Correct 514 ms 301816 KB Output is correct
4 Correct 503 ms 301112 KB Output is correct
5 Correct 478 ms 305056 KB Output is correct
6 Correct 693 ms 316624 KB Output is correct
7 Correct 714 ms 316612 KB Output is correct
8 Correct 668 ms 314448 KB Output is correct
9 Correct 459 ms 301628 KB Output is correct
10 Correct 463 ms 303560 KB Output is correct
11 Correct 451 ms 298596 KB Output is correct
12 Correct 460 ms 303472 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 797 ms 374372 KB Output is correct
2 Correct 772 ms 369844 KB Output is correct
3 Correct 517 ms 302248 KB Output is correct
4 Correct 578 ms 304796 KB Output is correct
5 Correct 518 ms 302832 KB Output is correct
6 Correct 786 ms 314512 KB Output is correct
7 Correct 849 ms 317996 KB Output is correct
8 Correct 834 ms 318528 KB Output is correct
9 Correct 674 ms 317092 KB Output is correct
10 Correct 715 ms 317732 KB Output is correct
11 Correct 616 ms 313512 KB Output is correct
12 Correct 712 ms 315996 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 362188 KB Output is correct
2 Correct 524 ms 362092 KB Output is correct
3 Correct 321 ms 292524 KB Output is correct
4 Correct 278 ms 292348 KB Output is correct
5 Correct 267 ms 292336 KB Output is correct
6 Correct 359 ms 306416 KB Output is correct
7 Correct 407 ms 306416 KB Output is correct
8 Correct 416 ms 305168 KB Output is correct
9 Correct 349 ms 304620 KB Output is correct
10 Correct 334 ms 304332 KB Output is correct
11 Correct 375 ms 302828 KB Output is correct
12 Correct 393 ms 304360 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1388 ms 453248 KB Output is correct
2 Correct 1334 ms 453084 KB Output is correct
3 Correct 755 ms 313660 KB Output is correct
4 Correct 800 ms 312960 KB Output is correct
5 Correct 740 ms 313584 KB Output is correct
6 Correct 1084 ms 341476 KB Output is correct
7 Correct 1125 ms 341472 KB Output is correct
8 Correct 1137 ms 341436 KB Output is correct
9 Correct 974 ms 337632 KB Output is correct
10 Correct 906 ms 337628 KB Output is correct
11 Correct 933 ms 337868 KB Output is correct
12 Correct 924 ms 337860 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1623 ms 465100 KB Output is correct
2 Correct 1645 ms 464452 KB Output is correct
3 Correct 928 ms 321956 KB Output is correct
4 Correct 1028 ms 326912 KB Output is correct
5 Correct 984 ms 320860 KB Output is correct
6 Correct 1589 ms 354400 KB Output is correct
7 Correct 1360 ms 349840 KB Output is correct
8 Correct 1409 ms 352748 KB Output is correct
9 Correct 1222 ms 348236 KB Output is correct
10 Correct 1172 ms 346436 KB Output is correct
11 Correct 1161 ms 347012 KB Output is correct
12 Correct 1177 ms 348900 KB Output is correct