| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 653207 | Rafi22 | Prize (CEOI22_prize) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
//#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=1000007;
vector<int>G1[N],G2[N],G3[N];
int d1[N],d2[N];
bool odw[N];
vector<pair<int,int>>X[N],X1[N];
bool is[N];
int n,k,q,t;
int skok[N][20];
int pre[N];
int post[N];
int c=0;
void dfs(int v,int o)
{
pre[v]=++c;
skok[v][0]=o;
for(int i=1;i<20;i++) skok[v][i]=skok[skok[v][i-1]][i-1];
if(k>0)
{
cout<<v<<" ";
is[v]=1;
k--;
}
for(auto u:G1[v]) dfs(u,v);
post[v]=++c;
}
int lca(int u,int v)
{
if(pre[u]<=pre[v]&&post[u]>=post[v]) return u;
if(pre[v]<=pre[u]&&post[v]>=post[u]) return v;
for(int i=19;i>=0;i--) if(!(pre[skok[u][i]]<=pre[v]&&post[skok[u][i]]>=post[v])) u=skok[u][i];
return skok[u][0];
}
vector<pair<pair<int,int>,int>>xd;
void qry(int u,int v,int x)
{
if(!is[u]||!is[v]) for(int i=0;i<1000000000;i++) dfs(1,0);
cout<<"? "<<u<<" "<<v<<endl;
xd.pb({{u,v},x});
}
int last[N];
int last1[N];
int pre1[N];
int post1[N];
void dfs1(int v)
{
pre1[v]=c++;
int l=0,l1=0,cc=0;
for(auto u:G2[v])
{
dfs1(u);
if(last[u]>0)
{
cc++;
if(is[v])
{
G3[v].pb(last1[u]);
qry(last[u],v,v);
}
else if(cc>1)
{
if(cc==2) G3[v].pb(l1);
G3[v].pb(last1[u]);
qry(l,last[u],v);
}
else
{
l=last[u];
l1=last1[u];
}
}
}
if(is[v]) last[v]=v;
else last[v]=l;
if(is[v]||cc>1) last1[v]=v;
else last1[v]=l1;
post1[v]=c++;
}
int skok1[N][20];
void dfs2(int v,int o)
{
pre1[v]=c++;
skok1[v][0]=o;
for(int i=1;i<20;i++) skok1[v][i]=skok1[skok1[v][i-1]][i-1];
for(auto u:G3[v]) dfs2(u,v);
post1[v]=c++;
}
int lca1(int u,int v)
{
if(pre1[u]<=pre1[v]&&post1[u]>=post1[v]) return u;
if(pre1[v]<=pre1[u]&&post1[v]>=post1[u]) return v;
for(int i=19;i>=0;i--) if(!(pre1[skok1[u][i]]<=pre1[v]&&post1[skok1[u][i]]>=post1[v])) u=skok1[u][i];
return skok1[u][0];
}
int U[N],V[N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k>>q>>t;
int K=k;
int r1,r2,p;
for(int i=1;i<=n;i++)
{
cin>>p;
if(p==-1) r1=i;
else G1[p].pb(i);
}
for(int i=1;i<=n;i++)
{
cin>>p;
if(p==-1) r2=i;
else G2[p].pb(i);
}
dfs(r1,r1);
cout<<endl;
c=0;
dfs1(r2);
if(sz(xd)>K)
{
return 2137;
// for(int i=0;i<100000000;i++) dfs(1,0);
}
cout<<"!"<<endl;
for(auto c:xd)
{
int u=c.st.st,v=c.st.nd,x=c.nd;
int d1,d2,d3,d4;
cin>>d1>>d2>>d3>>d4;
int l=lca(u,v);
X[l].pb({u,d1});
X[u].pb({l,d1});
X[l].pb({v,d2});
X[v].pb({l,d2});
X1[x].pb({u,d3});
X1[u].pb({x,d3});
X1[x].pb({v,d4});
X1[v].pb({x,d4});
}
c=0;
dfs2(last1[r2],last1[r2]);
deque<int>Q;
Q.pb(r1);
odw[r1]=1;
while(sz(Q)>0)
{
int v=Q[0];
Q.pop_front();
for(auto x:X[v])
{
if(odw[x.st]) continue;
odw[x.st]=1;
Q.pb(x.st);
if(pre[x.st]>=pre[v]) d1[x.st]=d1[v]+x.nd;
else d1[x.st]=d1[v]-x.nd;
}
}
memset(odw,0,sizeof odw);
Q.pb(r2);
odw[r2]=1;
while(sz(Q)>0)
{
int v=Q[0];
Q.pop_front();
for(auto x:X1[v])
{
if(odw[x.st]) continue;
odw[x.st]=1;
Q.pb(x.st);
if(pre1[x.st]>=pre1[v]) d2[x.st]=d2[v]+x.nd;
else d2[x.st]=d2[v]-x.nd;
}
}
for(int i=1;i<=t;i++) cin>>U[i]>>V[i];
for(int i=1;i<=t;i++)
{
int u=U[i],v=V[i];
int l=lca(u,v);
cout<<d1[u]+d1[v]-2*d1[l]<<" ";
l=lca1(u,v);
cout<<d2[u]+d2[v]-2*d2[l]<<endl;
}
return 0;
}