oj.uz

Submission #858786

# Submission time Handle Problem Language Result Execution time Memory
858786 2023-10-09T07:44:56 Z Andrei Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 455080 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 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 1971 ms 248320 KB Output is correct
2 Correct 2125 ms 251844 KB Output is correct
3 Correct 1002 ms 211732 KB Output is correct
4 Correct 979 ms 211320 KB Output is correct
5 Correct 1040 ms 213544 KB Output is correct
6 Correct 1724 ms 220332 KB Output is correct
7 Correct 1760 ms 220264 KB Output is correct
8 Correct 1663 ms 218528 KB Output is correct
9 Correct 1043 ms 211052 KB Output is correct
10 Correct 1014 ms 212376 KB Output is correct
11 Correct 955 ms 209028 KB Output is correct
12 Correct 995 ms 210412 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2153 ms 251256 KB Output is correct
2 Correct 2035 ms 248512 KB Output is correct
3 Runtime error 973 ms 209372 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 1637 ms 245096 KB Output is correct
2 Correct 1630 ms 241528 KB Output is correct
3 Runtime error 686 ms 204440 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 3608 ms 455080 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 3578 ms 448344 KB Time limit exceeded
2 Halted 0 ms 0 KB -