oj.uz

Submission #882137

# Submission time Handle Problem Language Result Execution time Memory
882137 2023-12-02T16:38:23 Z AndrijaM Regions (IOI09_regions) C++14
23 / 100
 8000 ms 56992 KB 
#include <bits/stdc++.h>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<utility>
#include<map>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;

const long long maxn=2e5+15;
const long long logn=23;
long long up_node[maxn][logn];
long long d[maxn];
vector<long long>g[maxn];
int di[8]={0,0,1,-1,1,-1,1,-1};
int dj[8]={1,-1,0,0,1,-1,-1,1};
vector<int>ras[25001];

int n,r,q;

void dfs(long long node)
{
    d[node]=d[up_node[node][0]]+1;
    for(long long i=1;i<logn;i++)
    {
        up_node[node][i]=up_node[up_node[node][i-1]][i-1];
    }
    for(auto ax:g[node])
    {
        dfs(ax);
    }
}

long long UP(long long node,long long k)
{
    for(long long i=0;i<logn;i++)
    {
        if(k&(1<<i))
        {
            node=up_node[node][i];
        }
    }
    return node;
}

long long LCA(long long a,long long b)
{
    if(d[a]<d[b])
    {
        swap(a,b);
    }
    long long k=d[a]-d[b];
    a=UP(a,k);
    if(a==b)
    {
        return a;
    }
    for(long long i=logn-1;i>=0;i--)
    {
        if(up_node[a][i]!=up_node[b][i])
        {
            a=up_node[a][i];
            b=up_node[b][i];
        }
    }
    return up_node[a][0];
}

int main()///SQRT havey/light
{
    ///freopen("maxflow.in","r",stdin);
	///freopen("maxflow.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>r>>q;
    int P,R;
    cin>>R;
    ras[R].push_back(1);
    for(int i=2;i<=n;i++)
    {
        cin>>P>>R;
        up_node[i][0]=P;
        ras[R].push_back(i);
        g[P].push_back(i);
    }
    dfs(1);
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        int ans=0;
        for(auto ax:ras[a])
        {
            for(auto ay:ras[b])
            {
                int N=LCA(ax,ay);
                if(N==ax)
                {
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 4 ms 8792 KB Output is correct
5 Correct 16 ms 8952 KB Output is correct
6 Correct 14 ms 8792 KB Output is correct
7 Correct 54 ms 8792 KB Output is correct
8 Correct 61 ms 8792 KB Output is correct
9 Correct 115 ms 9048 KB Output is correct
10 Correct 599 ms 11096 KB Output is correct
11 Correct 4273 ms 11440 KB Output is correct
12 Correct 3506 ms 13652 KB Output is correct
13 Correct 7854 ms 13400 KB Output is correct
14 Execution timed out 8086 ms 13988 KB Time limit exceeded
15 Execution timed out 8054 ms 17756 KB Time limit exceeded

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8029 ms 24320 KB Time limit exceeded
2 Execution timed out 8025 ms 25160 KB Time limit exceeded
3 Execution timed out 8047 ms 29652 KB Time limit exceeded
4 Correct 4570 ms 13912 KB Output is correct
5 Correct 5495 ms 17196 KB Output is correct
6 Execution timed out 8077 ms 18976 KB Time limit exceeded
7 Execution timed out 8007 ms 23644 KB Time limit exceeded
8 Execution timed out 8057 ms 33304 KB Time limit exceeded
9 Execution timed out 8060 ms 41556 KB Time limit exceeded
10 Execution timed out 8089 ms 49100 KB Time limit exceeded
11 Execution timed out 8058 ms 48788 KB Time limit exceeded
12 Execution timed out 8016 ms 48692 KB Time limit exceeded
13 Execution timed out 8013 ms 48612 KB Time limit exceeded
14 Execution timed out 8015 ms 50088 KB Time limit exceeded
15 Execution timed out 8095 ms 53272 KB Time limit exceeded
16 Execution timed out 8067 ms 56992 KB Time limit exceeded
17 Execution timed out 8099 ms 56064 KB Time limit exceeded