oj.uz

Submission #1044027

# Submission time Handle Problem Language Result Execution time Memory
1044027 2024-08-05T06:30:34 Z ㅇㅇ(#11061) Prize (CEOI22_prize) C++17
0 / 100
 1316 ms 463228 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];
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;
		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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 548 ms 368512 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 585 ms 372616 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 445 ms 361592 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1219 ms 449608 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1316 ms 463228 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -