oj.uz

Submission #653215

# Submission time Handle Problem Language Result Execution time Memory
653215 2022-10-26T08:50:20 Z Rafi22 Prize (CEOI22_prize) C++14
0 / 100
 2439 ms 380328 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;

bool is[N];
int n,k,q,t;

struct tree
{
    vector<int>G[N];
    int pre[N];
    int post[N];
    int root;
    int skok[N][20];
    int d[N];
    vector<pair<int,int>>X[N];
    bool odw[N];
    int c=0;
    void dfs_lca(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];
        for(auto u:G[v]) dfs_lca(u,v);
        post[v]=++c;
    }
    bool anc(int u,int v)
    {
        return pre[u]<=pre[v]&&post[u]>=post[v];
    }
    int lca(int u,int v)
    {
        if(anc(u,v)) return u;
        if(anc(v,u)) return v;
        for(int i=19;i>=0;i--) if(!anc(skok[u][i],v)) u=skok[u][i];
        return skok[u][0];
    }
    void get_d()
    {
        for(int i=1;i<=n;i++) odw[i]=0;
        odw[root]=1;
        d[root]=0;
        deque<int>Q;
        Q.pb(root);
        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]) d[x.st]=d[v]+x.nd;
                else d[x.st]=d[v]-x.nd;
            }
        }
    }
};

tree T1,T2;

void dfs_k(int v)
{
    if(k>0)
    {
        cout<<v<<" ";
        is[v]=1;
        k--;
    }
    for(auto u:T1.G[v]) dfs_k(u);
}

vector<int>V;

void dfs1(int v)
{
    if(is[v]) V.pb(v);
    for(auto u:T2.G[v]) dfs1(u);
}

int A[N],B[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>q>>t;
    int K=k,p;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==-1) T1.root=i;
        else T1.G[p].pb(i);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==-1) T2.root=i;
        else T2.G[p].pb(i);
    }
    dfs_k(T1.root);
    cout<<endl;
    T1.dfs_lca(T1.root,T1.root);
    T2.dfs_lca(T2.root,T2.root);
    dfs1(T2.root);
    for(int i=1;i<k;i++) cout<<"? "<<V[i-1]<<" "<<V[i]<<endl;
    cout<<"!"<<endl;
    for(int i=1;i<k;i++)
    {
        int u=V[i-1],v=V[i];
        int d1,d2,d3,d4;
        cin>>d1>>d2>>d3>>d4;
        int l=T1.lca(u,v);
        T1.X[l].pb({u,d1});
        T1.X[u].pb({l,d1});
        T1.X[l].pb({v,d2});
        T1.X[v].pb({l,d2});
        l=T2.lca(u,v);
        T2.X[l].pb({u,d3});
        T2.X[u].pb({l,d3});
        T2.X[l].pb({v,d4});
        T2.X[v].pb({l,d4});
    }
    T1.get_d();
    T2.get_d();
    for(int i=1;i<=t;i++) cin>>A[i]>>B[i];
    for(int i=1;i<=t;i++)
    {
        int u=A[i],v=B[i];
        int l=T1.lca(u,v);
        cout<<T1.d[u]+T1.d[v]-2*T1.d[l]<<" ";
        l=T2.lca(u,v);
        cout<<T2.d[u]+T2.d[v]-2*T2.d[l]<<endl;
    }


    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:104:9: warning: unused variable 'K' [-Wunused-variable]
  104 |     int K=k,p;
      |         ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1137 ms 237996 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 1074 ms 236948 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 2306 ms 379852 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 2439 ms 380328 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -