oj.uz

Submission #653121

# Submission time Handle Problem Language Result Execution time Memory
653121 2022-10-25T18:52:54 Z Rafi22 Prize (CEOI22_prize) C++14
10 / 100
 1967 ms 430188 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];
vector<pair<int,int>>G3[N];
int d1[N],d2[N];
bool odw[N];
vector<pair<int,int>>X[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];

void dfs1(int v)
{
    int l=0,c=0;
    for(auto u:G2[v])
    {
        dfs1(u);
        if(last[u]>0)
        {
            c++;
            if(is[v]) qry(last[u],v,v);
            else if(c>1) qry(l,last[u],v);
            else l=last[u];
        }
    }
    if(is[v]||c>1) last[v]=v;
    else if(c==1) last[v]=l;
}

int skok1[N][20];
int pre1[N];
int post1[N];

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])
    {
        d2[u.st]=d2[v]+u.nd;
        dfs2(u.st,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 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;
    dfs1(r2);
    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});
        if(v!=x) G3[x].pb({v,d4});
        G3[x].pb({u,d3});
    }
    c=0;
    dfs2(last[r2],last[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;
        }
    }
    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;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:151:12: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  151 |     odw[r1]=1;
      |     ~~~~~~~^~
Main.cpp:148:9: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |     dfs2(last[r2],last[r2]);
      |     ~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 264300 KB Output is correct
2 Correct 1053 ms 267060 KB Output is correct
3 Correct 793 ms 210556 KB Output is correct
4 Correct 800 ms 209992 KB Output is correct
5 Correct 921 ms 212276 KB Output is correct
6 Correct 1157 ms 222708 KB Output is correct
7 Correct 1165 ms 222448 KB Output is correct
8 Correct 1099 ms 221816 KB Output is correct
9 Correct 832 ms 210172 KB Output is correct
10 Correct 880 ms 211568 KB Output is correct
11 Correct 803 ms 208972 KB Output is correct
12 Correct 813 ms 211456 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 267180 KB Output is correct
2 Correct 973 ms 263192 KB Output is correct
3 Runtime error 450 ms 156212 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1025 ms 214616 KB Output is correct
2 Correct 928 ms 214600 KB Output is correct
3 Runtime error 456 ms 155036 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1671 ms 342180 KB Output is correct
2 Correct 1724 ms 342532 KB Output is correct
3 Runtime error 935 ms 217024 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1967 ms 430188 KB Output is correct
2 Correct 1929 ms 429320 KB Output is correct
3 Runtime error 918 ms 217852 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -