Submission #1119985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119985		PieArmy	Prize (CEOI22_prize)	C++17	100 / 100	2787 ms	526016 KiB

Main

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
#define int ll
int n,k,q,t;
int tim=1;
vector<int>child[2][1000001];
int ord[1000001],par[2][1000001][20],root[2],dep[2][1000001],dis[2][1000001];
vector<int>v;

void dfs(int pos,int o){
	for(int i=1;i<20;i++){
		par[o][pos][i]=par[o][par[o][pos][i-1]][i-1];
	}
	if(o)ord[pos]=tim++;
	for(int x:child[o][pos]){
		dep[o][x]=dep[o][pos]+1;
		dfs(x,o);
	}
}

int lca(int a,int b,int o){
	if(dep[o][a]<dep[o][b])swap(a,b);
	for(int i=0;i<20;i++){
		if((dep[o][a]-dep[o][b])&pie(i)){
			a=par[o][a][i];
		}
	}
	if(a==b)return a;
	for(int i=20-1;i>=0;i--){
		if(par[o][a][i]!=par[o][b][i]){
			a=par[o][a][i];
			b=par[o][b][i];
		}
	}
	return par[o][a][0];
}

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>k>>q>>t;
	for(int i=0;i<2;i++){
		for(int j=1;j<=n;j++){
			cin>>par[i][j][0];
			if(par[i][j][0]==-1){
				par[i][j][0]=0;
				root[i]=j;
				continue;
			}
			child[i][par[i][j][0]].pb(j);
		}
	}
	dfs(root[0],0);
	dfs(root[1],1);
	queue<int>qu;
	qu.push(root[0]);
	while(qu.size()){
		int pos=qu.front();
		qu.pop();
		v.pb(pos);
		if(v.size()==k)break;
		for(int x:child[0][pos]){
			qu.push(x);
		}
	}
	sort(v.begin(),v.end(),[&](const int &x,const int &y){
		return ord[x]<ord[y];
	});
	for(int x:v){
		cout<<x<<" ";
	}
	cout<<'\n';
	for(int i=1;i<k;i++){
		cout<<"? "<<v[i-1]<<" "<<v[i]<<'\n';
	}
	cout<<"!"<<endl;
	for(int i=1;i<k;i++){
		int res[2][2];
		cin>>res[0][0]>>res[0][1]>>res[1][0]>>res[1][1];
		int lca_[2];
		lca_[0]=lca(v[i-1],v[i],0);
		lca_[1]=lca(v[i-1],v[i],1);
		dis[0][lca_[0]]=dis[0][v[i-1]]-res[0][0];
		dis[1][lca_[1]]=dis[1][v[i-1]]-res[1][0];
		dis[0][v[i]]=dis[0][lca_[0]]+res[0][1];
		dis[1][v[i]]=dis[1][lca_[1]]+res[1][1];
	}
	pair<int,int>ans[t];
	for(int i=0;i<t;i++){
		int x,y;cin>>x>>y;
		ans[i]={dis[0][x]+dis[0][y]-(dis[0][lca(x,y,0)]*2),dis[1][x]+dis[1][y]-(dis[1][lca(x,y,1)]*2)};
	}
	for(int i=0;i<t;i++){
		cout<<ans[i].fr<<" "<<ans[i].sc<<endl;
	}
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:69:14: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   69 |   if(v.size()==k)break;
      |      ~~~~~~~~^~~

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