제출 #653143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653143		Rafi22	Prize (CEOI22_prize)	C++14	10 / 100	1828 ms	504904 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;

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,c=0;
    for(auto u:G2[v])
    {
        dfs1(u);
        if(last[u]>0)
        {
            c++;
            if(is[v])
            {
                G3[v].pb(last1[u]);
                qry(last[u],v,v);
            }
            else if(c>1)
            {
                if(c==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]||c>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;
}

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