oj.uz

Submission #858779

# Submission time Handle Problem Language Result Execution time Memory
858779 2023-10-09T07:41:13 Z Andrei Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 457092 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(N+1);
        for(int i=0; i<=N; i++)
            h[i].resize(20);

        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[v][0]=u;
            for(int j=1; (1<<j)<=depth[v]; j++)
                h[v][j]=h[h[v][j-1]][j-1];

            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[v][j];

        if(u==v)
            return u;

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

        return h[u][0];
    }

    int dist(int u,int v)
    {
        int l=lca(u,v);
        return distFromRoot[u]+distFromRoot[v]-2*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]-2*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 1907 ms 248420 KB Output is correct
2 Correct 2051 ms 252516 KB Output is correct
3 Correct 932 ms 211668 KB Output is correct
4 Correct 1045 ms 211212 KB Output is correct
5 Correct 1016 ms 212980 KB Output is correct
6 Correct 1607 ms 220628 KB Output is correct
7 Correct 1539 ms 220564 KB Output is correct
8 Correct 1539 ms 218288 KB Output is correct
9 Correct 921 ms 211620 KB Output is correct
10 Correct 945 ms 212300 KB Output is correct
11 Correct 906 ms 209264 KB Output is correct
12 Correct 964 ms 210340 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2401 ms 251112 KB Output is correct
2 Correct 2127 ms 248860 KB Output is correct
3 Runtime error 946 ms 209200 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 1642 ms 244736 KB Output is correct
2 Correct 1604 ms 241436 KB Output is correct
3 Runtime error 639 ms 204688 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3574 ms 455288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3540 ms 457092 KB Time limit exceeded
2 Halted 0 ms 0 KB -