oj.uz

Submission #936483

# Submission time Handle Problem Language Result Execution time Memory
936483 2024-03-02T00:41:05 Z Edu175 Prize (CEOI22_prize) C++17
10 / 100
 2260 ms 512616 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ceoi=b;i<ceoi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto kdjfhg:v)cout<<kdjfhg<<" ";cout<<"\n"
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=1e6+5,K=20;

vector<ii> g[2][MAXN]; ll n; ll rt[2];
struct LCA{
	vector<vector<ll>>F,V; vector<ll>D;
	LCA(): F(K,vector<ll>(1<<K)),V(K,vector<ll>(1<<K)),D(MAXN){}
	void lca_dfs(ll x, ll z){
		for(auto [y,w]:g[z][x])if(y!=F[0][x]){
			F[0][y]=x;
			V[0][y]=w;
			D[y]=D[x]+1;
			lca_dfs(y,z);
		}
	}
	void lca_init(ll rt, ll z){
		D[rt]=V[0][rt]=0;F[0][rt]=-1;
		lca_dfs(rt,z);
		fore(k,1,K)fore(i,0,n){
			if(F[k-1][i]<0)F[k][i]=-1,V[k][i]=V[k-1][i];
			else {
				F[k][i]=F[k-1][F[k-1][i]];
				V[k][i]=V[k-1][i]+V[k-1][F[k-1][i]];
			}
		}
	}
	ii lca(ll x, ll y){
		if(D[x]<D[y])swap(x,y);
		ll res=0;
		for(ll k=K-1;k>=0;k--)if(D[x]-(1ll<<k)>=D[y]){
			res+=V[k][x];
			x=F[k][x];
		}
		//cout<<"iguales?\n";
		if(x==y)return {x,res};
		//cout<<"no\n";
		for(ll k=K-1;k>=0;k--)if(F[k][x]!=F[k][y]){
			res+=V[k][x]+V[k][y];
			x=F[k][x];
			y=F[k][y];
		}
		res+=V[0][x]+V[0][y];
		x=F[0][x];
		return {x,res};
	}
};

vector<ll>nod;
void dfs(ll x, ll z){
	nod.pb(x);
	for(auto [y,c]:g[z][x])dfs(y,z);
}
int main(){
	ll k,q,t; cin>>n>>k>>q>>t;
	fore(h,0,2)fore(i,0,n){
		ll p; cin>>p; p--;
		if(p<0)rt[h]=i;
		else g[h][p].pb({i,0});
	}
	dfs(rt[0],0);
	nod.resize(k);
	LCA G1;
	G1.lca_init(rt[0],0);
	vector<ll>pa(n);
	fore(i,0,n)pa[i]=G1.F[0][i];
	for(auto i:nod)cout<<i+1<<" ";;cout<<endl;
	for(auto i:nod)if(pa[i]>=0)
		cout<<"? "<<i+1<<" "<<pa[i]+1<<endl;
	cout<<"!"<<endl;
	fore(i,0,n)g[0][i].clear();
	fore(i,0,SZ(nod))if(pa[nod[i]]>=0){
		//cout<<"ingresa "<<i<<endl;
		ll w=0;
		fore(j,0,4){
			ll x; cin>>x;
			w=max(w,x);
		}
		g[0][pa[nod[i]]].pb({nod[i],w});
	}
	//cout<<"termina"<<endl;
	G1.lca_init(rt[0],0);
	vector<ii>ans;
	while(t--){
		ll x,y; cin>>x>>y; x--,y--;
		ll r=G1.lca(x,y).snd;
		ans.pb({r,r});
	}
	for(auto i:ans)cout<<i.fst<<" "<<i.snd<<endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1302 ms 450788 KB Output is correct
2 Correct 1291 ms 451196 KB Output is correct
3 Correct 917 ms 421400 KB Output is correct
4 Correct 895 ms 421620 KB Output is correct
5 Correct 973 ms 421840 KB Output is correct
6 Correct 1189 ms 427064 KB Output is correct
7 Correct 1215 ms 427444 KB Output is correct
8 Correct 1207 ms 426832 KB Output is correct
9 Correct 922 ms 421960 KB Output is correct
10 Correct 937 ms 421564 KB Output is correct
11 Correct 910 ms 421160 KB Output is correct
12 Correct 992 ms 421660 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1190 ms 449992 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 871 ms 448020 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 2007 ms 512616 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2260 ms 512612 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -