oj.uz

Submission #858791

# Submission time Handle Problem Language Result Execution time Memory
858791 2023-10-09T07:49:20 Z Andrei Prize (CEOI22_prize) C++17
10 / 100
 3327 ms 388344 KB 
#include <bits/stdc++.h>

using namespace std;

int N,K,Q,T;

int r1;
int r2;

struct Tree
{
    int sz;

    int root;

    vector <int> par;

    int cnt;

    vector <int> tIn;
    vector <int> tOut;

    vector <vector <int>> g;

    vector <int> depth;

    vector <vector <int>> h;

    vector <int> distFromRoot;

    void buildg()
    {
        g.resize(N+1);

        tIn.resize(N+1);
        tOut.resize(N+1);

        depth.resize(N+1);

        h.resize(20);
        for(int j=0; j<=19; j++)
            h[j].resize(N+1);

        distFromRoot.resize(N+1);

        for(int i=1; i<=N; i++)
            if(par[i]>=1)
                g[par[i]].push_back(i);
    }

    void dfs(int u)
    {
        cnt++;

        tIn[u]=cnt;

        for(int v:g[u])
        {
            depth[v]=depth[u]+1;

            h[0][v]=u;
            for(int j=1; (1<<j)<=depth[v]; j++)
                h[j][v]=h[j-1][h[j-1][v]];

            dfs(v);
        }

        tOut[u]=cnt;
    }

    bool inSubtreeOf(int u,int v)
    {
        return (tIn[v]>=tIn[u] && tOut[v]<=tOut[u]);
    }

    int lca(int u,int v)
    {
        if(depth[v]<depth[u])
            swap(u,v);
        for(int j=19; j>=0; j--)
            if((depth[v]-depth[u])&(1<<j))
                v=h[j][v];

        if(u==v)
            return u;

        for(int j=19; j>=0; j--)
        {
            if(h[j][u]!=h[j][v])
            {
                u=h[j][u];
                v=h[j][v];
            }
        }

        return h[0][u];
    }

    int dist(int u,int v)
    {
        int l=lca(u,v);
        return 1LL*distFromRoot[u]+distFromRoot[v]-2LL*distFromRoot[l];
    }
} T1,T2;

int L2;

vector <pair <int,int>> g[1000005];

void add(int u,int v)
{
    if(L2==0 || T2.depth[u]<T2.depth[L2])
        L2=u;
    if(T2.depth[v]<T2.depth[L2])
        L2=v;

    int x,y,z,w;
    cin>>x>>y>>z>>w;

    T1.distFromRoot[v]=T1.distFromRoot[u]+y;

    int lca2=T2.lca(u,v);

    if(T2.depth[lca2]<T2.depth[L2])
        L2=lca2;

    g[lca2].push_back(make_pair(u,z));
    g[u].push_back(make_pair(lca2,-z));
    g[lca2].push_back(make_pair(v,w));
    g[v].push_back(make_pair(lca2,-w));
}

int cnt;

void printNodes(int u)
{
    if(cnt<K)
        cout<<u<<" ";
    cnt++;
    for(int v:T1.g[u])
        printNodes(v);
}

void printQuestions(int u)
{
    for(int v:T1.g[u])
    {
        if(cnt<K-1)
            cout<<"? "<<r1<<" "<<v<<"\n";
        cnt++;
        printQuestions(v);
    }
}

void dfs(int u)
{
    for(int v:T1.g[u])
    {
        if(cnt<K-1)
            add(r1,v);
        cnt++;
        dfs(v);
    }
}

queue <int> q;

bool viz[1000005];

int dist[1000005];

vector <pair <int,int>> ans;

int main()
{
    cin>>N>>K>>Q>>T;

    T1.par.resize(N+1);
    T2.par.resize(N+1);
    for(int i=1; i<=N; i++)
    {
        cin>>T1.par[i];
        if(T1.par[i]==-1)
            r1=i;
    }
    for(int i=1; i<=N; i++)
    {
        cin>>T2.par[i];
        if(T2.par[i]==-1)
            r2=i;
    }

    T1.buildg();
    T1.dfs(r1);

    T2.buildg();
    T2.dfs(r2);

    printNodes(r1);
    cout<<endl;

    cnt=0;
    printQuestions(r1);
    cout.flush();

    cout<<"!"<<endl;

    cnt=0;
    dfs(r1);

    q.push(L2);
    viz[L2]=1;

    while(!q.empty())
    {
        int x=q.front();
        q.pop();

        for(pair <int,int> edge:g[x])
        {
            if(viz[edge.first]==0)
            {
                viz[edge.first]=1;
                dist[edge.first]=dist[x]+edge.second;
                q.push(edge.first);
            }
        }
    }

    while(T--)
    {
        int p,q;
        cin>>p>>q;

        int lca2=T2.lca(p,q);

        ans.push_back(make_pair(T1.dist(p,q),1LL*dist[p]+dist[q]-2LL*dist[lca2]));
    }

    for(auto it:ans)
        cout<<it.first<<" "<<it.second<<"\n";
    cout.flush();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1561 ms 209580 KB Output is correct
2 Correct 1588 ms 213708 KB Output is correct
3 Correct 903 ms 172492 KB Output is correct
4 Correct 873 ms 172268 KB Output is correct
5 Correct 923 ms 176312 KB Output is correct
6 Correct 1429 ms 181616 KB Output is correct
7 Correct 1469 ms 181032 KB Output is correct
8 Correct 1426 ms 179216 KB Output is correct
9 Correct 857 ms 172488 KB Output is correct
10 Correct 930 ms 173336 KB Output is correct
11 Correct 836 ms 169752 KB Output is correct
12 Correct 883 ms 171540 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1674 ms 212084 KB Output is correct
2 Correct 1556 ms 209864 KB Output is correct
3 Runtime error 897 ms 170152 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 1245 ms 205916 KB Output is correct
2 Correct 1263 ms 202636 KB Output is correct
3 Runtime error 625 ms 165836 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 2976 ms 382060 KB Output is correct
2 Correct 2880 ms 381900 KB Output is correct
3 Runtime error 1435 ms 304648 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 3275 ms 388344 KB Output is correct
2 Correct 3327 ms 388240 KB Output is correct
3 Runtime error 1580 ms 309076 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -