oj.uz

Submission #858783

# Submission time Handle Problem Language Result Execution time Memory
858783 2023-10-09T07:43:18 Z Andrei Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 457112 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]-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 1980 ms 247760 KB Output is correct
2 Correct 2343 ms 253900 KB Output is correct
3 Correct 1018 ms 211520 KB Output is correct
4 Correct 965 ms 211196 KB Output is correct
5 Correct 1042 ms 213064 KB Output is correct
6 Correct 1651 ms 220672 KB Output is correct
7 Correct 1613 ms 220844 KB Output is correct
8 Correct 1603 ms 218340 KB Output is correct
9 Correct 914 ms 211208 KB Output is correct
10 Correct 959 ms 212324 KB Output is correct
11 Correct 927 ms 209124 KB Output is correct
12 Correct 954 ms 210064 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2142 ms 251116 KB Output is correct
2 Correct 1938 ms 248272 KB Output is correct
3 Runtime error 933 ms 209280 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 1563 ms 245348 KB Output is correct
2 Correct 1555 ms 241676 KB Output is correct
3 Runtime error 614 ms 204500 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 3585 ms 455104 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 457112 KB Time limit exceeded
2 Halted 0 ms 0 KB -