Submission #1231442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231442		alexander707070	Prize (CEOI22_prize)	C++20	0 / 100	3602 ms	463768 KiB

Main

#include<bits/stdc++.h>
#define MAXN 1000007

using namespace std;

struct answer{
    long long d1,d2,e1,e2;
}ans[MAXN];

struct path{
    int lca,a,b;
    long long da,db;
}s[MAXN];

int n,k,q,T,p,rootv,rootw,a,b;
vector<int> v[MAXN],w[MAXN];

vector<int> tree[MAXN];

vector<int> sp,euler;
bool vis[MAXN];
int root,dep[MAXN],parent[MAXN];
int len[MAXN],par[MAXN];

long long val[MAXN],dist[MAXN],pref[MAXN],pref2[MAXN];
pair<long long,long long> res[MAXN];
vector< pair<int,long long> > g[MAXN];

int up[MAXN][22],up2[MAXN][22];

void dfs(int x,int p){

    len[x]=len[p]+1;
    par[x]=p;

    if(int(sp.size())<k){
        sp.push_back(x);
        vis[x]=true;
    }

    for(int i:v[x]){
        dfs(i,x);
    }
}

int dfs2(int x,int p){

    vector<int> ch;
    for(int i:w[x]){
        int curr=dfs2(i,x);
        if(curr!=0)ch.push_back(curr);
    }

    if(!vis[x]){
        if(ch.empty())return 0;
        if(ch.size()==1)return ch[0];
    }

    for(int f:ch)tree[x].push_back(f);
    return x;
}

void dfs3(int x,int p){
    dep[x]=dep[p]+1;
    parent[x]=p;

    if(vis[x])euler.push_back(x);
    for(int i:tree[x])dfs3(i,x);
}

int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])x=parent[x];

    while(x!=y){
        x=parent[x];
        y=parent[y];
    }

    return x;
}

int lca2(int x,int y){
    if(len[x]<len[y])swap(x,y);
    while(len[x]>len[y])x=par[x];

    while(x!=y){
        x=par[x];
        y=par[y];
    }

    return x;
}

bool cmp(path fr,path sc){
    return dep[fr.lca] > dep[sc.lca];
}

void solve_up(int x,long long d){
    if(x==0)return;

    if(dist[x]==0){
        dist[x]=d; return;
    }

    solve_up(parent[x],d-dist[x]);
}

void dfs4(int x,long long d){
    pref[x]=d;
    vis[x]=true;

    for(auto nxt:g[x]){
        if(vis[nxt.first])continue;
        dfs4(nxt.first,d+nxt.second);
    }
}

void dfs5(int x,long long d){
    pref2[x]=d;

    for(auto nxt:tree[x]){
        dfs5(nxt,d+dist[nxt]);
    }
}

pair<long long,long long> dists(int x,int y){
    int xx=x,yy=y;

    if(len[x]<len[y])swap(x,y);

    int raz=len[x]-len[y];
    for(int i=19;i>=0;i--){
        if((1<<i)&raz)x=up[x][i];
    }
    
    /*while(x!=y){
        x=par[x];
        y=par[y];
    }*/

    /*for(int i=19;i>=0;i--){
        if((1<<i)<len[x] and up[x][i]!=up[y][i]){
            x=up[x][i];
            y=up[y][i];
        }
    }*/

    x=par[x];

    long long s1=pref[xx]+pref[yy]-2*pref[x];

    x=xx; y=yy;
    if(dep[x]<dep[y])swap(x,y);

    raz=dep[x]-dep[y];
    for(int i=19;i>=0;i--){
        if((1<<i)&raz)x=up2[x][i];
    }
    
    while(x!=y){
        x=parent[x];
        y=parent[y];
    }
    /*for(int i=19;i>=0;i--){
        if(up2[x][i]!=0 and up2[y][i]!=0 and up2[x][i]!=up2[y][i]){
            x=up2[x][i];
            y=up2[y][i];
        }
    }
    x=parent[x];*/

    long long s2=pref2[xx]+pref2[yy]-2*pref2[x];

    return {s1,s2};
}

int main(){
    
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);

    cin>>n>>k>>q>>T;

    for(int i=1;i<=n;i++){
        cin>>p;
        if(p!=-1)v[p].push_back(i);
        else rootv=i;
    }

    dfs(rootv,0);

    for(int i=1;i<=n;i++){
        cin>>p;
        if(p!=-1)w[p].push_back(i);
        else rootw=i;
    }

    root=dfs2(rootw,0);
    dfs3(root,0);

    for(int i:sp)cout<<i<<" ";
    cout<<"\n";
    for(int i=0;i<k-1;i++)cout<<"? "<<euler[i]<<" "<<euler[i+1]<<"\n";
    cout<<"!\n";

    cout<<flush;
    fflush(stdout);

    for(int i=0;i<k-1;i++){

        cin>>ans[i].d1>>ans[i].d2>>ans[i].e1>>ans[i].e2;
        s[i]={lca(euler[i],euler[i+1]),euler[i],euler[i+1],ans[i].e1,ans[i].e2};
    }

    sort(s,s+k-1,cmp);

    for(int i=0;i<k-1;i++){
        solve_up(s[i].a,s[i].da);
        solve_up(s[i].b,s[i].db);
    }

    for(int i=0;i<k-1;i++){
        int c=lca2(euler[i],euler[i+1]);

        g[c].push_back({euler[i],ans[i].d1});
        g[euler[i]].push_back({c,-ans[i].d1});

        g[c].push_back({euler[i+1],ans[i].d2});
        g[euler[i+1]].push_back({c,-ans[i].d2});
    }

    for(int i=1;i<=n;i++)vis[i]=false;
    
    dfs4(rootv,0);
    dfs5(root,0);

    for(int i=1;i<=n;i++){
        if(par[i]==-1)par[i]=0;
        if(parent[i]==-1)parent[i]=0;

        up[i][0]=par[i]; up2[i][0]=parent[i];
    }

    up[0][0]=up2[0][0]=0;

    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            up[i][j]=up[up[i][j-1]][j-1];
            up2[i][j]=up2[up2[i][j-1]][j-1];
        }
    }

    for(int i=1;i<=T;i++){
        cin>>a>>b;
        res[i]=dists(a,b);
    }

    for(int i=1;i<=T;i++){
        cout<<res[i].first<<" "<<res[i].second<<"\n";
    }

    cout<<flush;
    fflush(stdout);
    
    return 0;
}

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