제출 #882137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882137		AndrijaM	Regions (IOI09_regions)	C++14	23 / 100	8099 ms	56992 KiB

regions

#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 / 15
• Subtask 2: 10 / 85