oj.uz

Submission #653381

# Submission time Handle Problem Language Result Execution time Memory
653381 2022-10-26T16:42:12 Z Rafi22 Prize (CEOI22_prize) C++14
100 / 100
 3044 ms 396988 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;
    int mn=inf,r=0;
    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);
        if(T2.pre[l]<mn)
        {
            mn=T2.pre[l];
            r=l;
        }
        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.root=r;
    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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1365 ms 247872 KB Output is correct
2 Correct 1426 ms 250316 KB Output is correct
3 Correct 1032 ms 210356 KB Output is correct
4 Correct 1029 ms 209720 KB Output is correct
5 Correct 1053 ms 212324 KB Output is correct
6 Correct 1464 ms 219484 KB Output is correct
7 Correct 1594 ms 219508 KB Output is correct
8 Correct 1585 ms 218768 KB Output is correct
9 Correct 1127 ms 210116 KB Output is correct
10 Correct 1398 ms 211572 KB Output is correct
11 Correct 1325 ms 208724 KB Output is correct
12 Correct 1063 ms 211232 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1388 ms 250616 KB Output is correct
2 Correct 1320 ms 246872 KB Output is correct
3 Correct 1099 ms 210520 KB Output is correct
4 Correct 1165 ms 212900 KB Output is correct
5 Correct 1152 ms 211212 KB Output is correct
6 Correct 1527 ms 217668 KB Output is correct
7 Correct 1666 ms 220744 KB Output is correct
8 Correct 1745 ms 221060 KB Output is correct
9 Correct 1417 ms 218940 KB Output is correct
10 Correct 1433 ms 220040 KB Output is correct
11 Correct 1421 ms 216352 KB Output is correct
12 Correct 1427 ms 219628 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1199 ms 238380 KB Output is correct
2 Correct 1276 ms 238340 KB Output is correct
3 Correct 821 ms 200040 KB Output is correct
4 Correct 859 ms 200060 KB Output is correct
5 Correct 835 ms 199924 KB Output is correct
6 Correct 1106 ms 208500 KB Output is correct
7 Correct 1105 ms 208632 KB Output is correct
8 Correct 1097 ms 208488 KB Output is correct
9 Correct 975 ms 206560 KB Output is correct
10 Correct 918 ms 206448 KB Output is correct
11 Correct 1227 ms 206336 KB Output is correct
12 Correct 1187 ms 206556 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2798 ms 384876 KB Output is correct
2 Correct 2505 ms 384912 KB Output is correct
3 Correct 1727 ms 308680 KB Output is correct
4 Correct 1732 ms 308576 KB Output is correct
5 Correct 1734 ms 308352 KB Output is correct
6 Correct 2543 ms 325436 KB Output is correct
7 Correct 2598 ms 325680 KB Output is correct
8 Correct 2225 ms 325548 KB Output is correct
9 Correct 2182 ms 321344 KB Output is correct
10 Correct 2055 ms 321272 KB Output is correct
11 Correct 2108 ms 321216 KB Output is correct
12 Correct 2374 ms 321332 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3007 ms 396988 KB Output is correct
2 Correct 2782 ms 396584 KB Output is correct
3 Correct 1934 ms 317404 KB Output is correct
4 Correct 2125 ms 321288 KB Output is correct
5 Correct 1976 ms 316564 KB Output is correct
6 Correct 2982 ms 338500 KB Output is correct
7 Correct 2750 ms 334096 KB Output is correct
8 Correct 3044 ms 336476 KB Output is correct
9 Correct 2616 ms 331768 KB Output is correct
10 Correct 2548 ms 330700 KB Output is correct
11 Correct 2606 ms 330648 KB Output is correct
12 Correct 2599 ms 332764 KB Output is correct