Submission #653381

#	Time	Username	Problem	Language	Result	Execution time	Memory
653381		Rafi22	Prize (CEOI22_prize)	C++14	100 / 100	3044 ms	396988 KiB

Main

#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;

bool is[N];
int n,k,q,t;

struct tree
{
    vector<int>G[N];
    int pre[N];
    int post[N];
    int root;
    int skok[N][20];
    int d[N];
    vector<pair<int,int>>X[N];
    bool odw[N];
    int c=0;
    void dfs_lca(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];
        for(auto u:G[v]) dfs_lca(u,v);
        post[v]=++c;
    }
    bool anc(int u,int v)
    {
        return pre[u]<=pre[v]&&post[u]>=post[v];
    }
    int lca(int u,int v)
    {
        if(anc(u,v)) return u;
        if(anc(v,u)) return v;
        for(int i=19;i>=0;i--) if(!anc(skok[u][i],v)) u=skok[u][i];
        return skok[u][0];
    }
    void get_d()
    {
        for(int i=1;i<=n;i++) odw[i]=0;
        odw[root]=1;
        d[root]=0;
        deque<int>Q;
        Q.pb(root);
        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]) d[x.st]=d[v]+x.nd;
                else d[x.st]=d[v]-x.nd;
            }
        }
    }
};

tree T1,T2;

void dfs_k(int v)
{
    if(k>0)
    {
        cout<<v<<" ";
        is[v]=1;
        k--;
    }
    for(auto u:T1.G[v]) dfs_k(u);
}

vector<int>V;

void dfs1(int v)
{
    if(is[v]) V.pb(v);
    for(auto u:T2.G[v]) dfs1(u);
}

int A[N],B[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>q>>t;
    int K=k,p;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==-1) T1.root=i;
        else T1.G[p].pb(i);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==-1) T2.root=i;
        else T2.G[p].pb(i);
    }
    dfs_k(T1.root);
    cout<<endl;
    T1.dfs_lca(T1.root,T1.root);
    T2.dfs_lca(T2.root,T2.root);
    dfs1(T2.root);
    for(int i=1;i<K;i++) cout<<"? "<<V[i-1]<<" "<<V[i]<<endl;
    cout<<"!"<<endl;
    int mn=inf,r=0;
    for(int i=1;i<K;i++)
    {
        int u=V[i-1],v=V[i];
        int d1,d2,d3,d4;
        cin>>d1>>d2>>d3>>d4;
        int l=T1.lca(u,v);
        T1.X[l].pb({u,d1});
        T1.X[u].pb({l,d1});
        T1.X[l].pb({v,d2});
        T1.X[v].pb({l,d2});
        l=T2.lca(u,v);
        if(T2.pre[l]<mn)
        {
            mn=T2.pre[l];
            r=l;
        }
        T2.X[l].pb({u,d3});
        T2.X[u].pb({l,d3});
        T2.X[l].pb({v,d4});
        T2.X[v].pb({l,d4});
    }
    T1.get_d();
    T2.root=r;
    T2.get_d();
    for(int i=1;i<=t;i++) cin>>A[i]>>B[i];
    for(int i=1;i<=t;i++)
    {
        int u=A[i],v=B[i];
        int l=T1.lca(u,v);
        cout<<T1.d[u]+T1.d[v]-2*T1.d[l]<<" ";
        l=T2.lca(u,v);
        cout<<T2.d[u]+T2.d[v]-2*T2.d[l]<<endl;
    }


    return 0;
}

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