oj.uz

Submission #858761

# Submission time Handle Problem Language Result Execution time Memory
858761 2023-10-09T07:11:41 Z Andrei Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 470864 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<<"? "<<u<<" "<<v<<"\n";
        cnt++;
        printQuestions(v);
    }
}

void dfs(int u)
{
    for(int v:T1.g[u])
    {
        if(cnt<K-1)
            add(u,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),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 2005 ms 254656 KB Output is correct
2 Correct 2142 ms 257404 KB Output is correct
3 Correct 1029 ms 210628 KB Output is correct
4 Correct 963 ms 210464 KB Output is correct
5 Correct 1049 ms 211372 KB Output is correct
6 Correct 1622 ms 221356 KB Output is correct
7 Correct 1633 ms 220528 KB Output is correct
8 Correct 1726 ms 219440 KB Output is correct
9 Correct 959 ms 210628 KB Output is correct
10 Correct 991 ms 211432 KB Output is correct
11 Correct 940 ms 208140 KB Output is correct
12 Correct 1034 ms 209496 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2262 ms 257672 KB Output is correct
2 Correct 2157 ms 256360 KB Output is correct
3 Runtime error 956 ms 209244 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 1631 ms 252684 KB Output is correct
2 Correct 1656 ms 249772 KB Output is correct
3 Runtime error 673 ms 204448 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 3586 ms 448120 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 3577 ms 470864 KB Time limit exceeded
2 Halted 0 ms 0 KB -