oj.uz

Submission #653141

# Submission time Handle Problem Language Result Execution time Memory
653141 2022-10-25T19:27:57 Z Rafi22 Prize (CEOI22_prize) C++14
10 / 100
 2245 ms 504728 KB 
#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)
{
    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;
    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1075 ms 316940 KB Output is correct
2 Correct 1231 ms 320588 KB Output is correct
3 Correct 1000 ms 240224 KB Output is correct
4 Correct 928 ms 239468 KB Output is correct
5 Correct 1008 ms 242912 KB Output is correct
6 Correct 1370 ms 256944 KB Output is correct
7 Correct 1286 ms 256772 KB Output is correct
8 Correct 1321 ms 255772 KB Output is correct
9 Correct 925 ms 239856 KB Output is correct
10 Correct 995 ms 241980 KB Output is correct
11 Correct 899 ms 237784 KB Output is correct
12 Correct 922 ms 241348 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1010 ms 318800 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 728 ms 265840 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1562 ms 416912 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2245 ms 504728 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -