oj.uz

Submission #653125

# Submission time Handle Problem Language Result Execution time Memory
653125 2022-10-25T19:00:10 Z Rafi22 Prize (CEOI22_prize) C++14
10 / 100
 2096 ms 430216 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 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;
    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});
        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:152:12: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  152 |     odw[r1]=1;
      |     ~~~~~~~^~
Main.cpp:149:9: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  149 |     dfs2(last[r2],last[r2]);
      |     ~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1029 ms 264476 KB Output is correct
2 Correct 1128 ms 266776 KB Output is correct
3 Correct 822 ms 210252 KB Output is correct
4 Correct 936 ms 210148 KB Output is correct
5 Correct 900 ms 212164 KB Output is correct
6 Correct 1175 ms 222544 KB Output is correct
7 Correct 1095 ms 222548 KB Output is correct
8 Correct 1083 ms 221832 KB Output is correct
9 Correct 827 ms 210200 KB Output is correct
10 Correct 920 ms 211556 KB Output is correct
11 Correct 789 ms 209196 KB Output is correct
12 Correct 790 ms 211176 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1092 ms 267136 KB Output is correct
2 Correct 980 ms 263232 KB Output is correct
3 Runtime error 451 ms 156300 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 763 ms 214552 KB Output is correct
2 Correct 769 ms 214420 KB Output is correct
3 Runtime error 456 ms 154956 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 1896 ms 342144 KB Output is correct
2 Correct 1638 ms 342476 KB Output is correct
3 Runtime error 924 ms 216336 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 1950 ms 430216 KB Output is correct
2 Correct 2096 ms 429340 KB Output is correct
3 Runtime error 1032 ms 217964 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -