oj.uz

Submission #653143

# Submission time Handle Problem Language Result Execution time Memory
653143 2022-10-25T19:30:49 Z Rafi22 Prize (CEOI22_prize) C++14
10 / 100
 1828 ms 504904 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)
{
    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1092 ms 316804 KB Output is correct
2 Correct 1251 ms 320548 KB Output is correct
3 Correct 965 ms 239900 KB Output is correct
4 Correct 957 ms 239340 KB Output is correct
5 Correct 1006 ms 242896 KB Output is correct
6 Correct 1251 ms 256708 KB Output is correct
7 Correct 1256 ms 256780 KB Output is correct
8 Correct 1275 ms 255864 KB Output is correct
9 Correct 913 ms 239620 KB Output is correct
10 Correct 937 ms 241936 KB Output is correct
11 Correct 894 ms 238028 KB Output is correct
12 Correct 979 ms 241452 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 984 ms 318744 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 740 ms 265956 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 1594 ms 416980 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 1828 ms 504904 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -