oj.uz

Submission #653118

# Submission time Handle Problem Language Result Execution time Memory
653118 2022-10-25T18:43:28 Z Rafi22 Prize (CEOI22_prize) C++14
0 / 100
 1440 ms 325804 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];
}

void qry(int u,int v,int x)
{
    cout<<"? "<<u<<" "<<v<<endl;
    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});
}

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 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);
    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;
        }
    }
    while(t--)
    {
        int u,v;
        cin>>u>>v;
        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:140:12: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  140 |     odw[r1]=1;
      |     ~~~~~~~^~
Main.cpp:137:9: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  137 |     dfs2(last[r2],last[r2]);
      |     ~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 694 ms 208280 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 701 ms 208256 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 670 ms 209964 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1440 ms 325804 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1428 ms 322408 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -