Submission #653652

#	Time	Username	Problem	Language	Result	Execution time	Memory
653652		Kaang	트리 (KOI16_tree)	C++17	0 / 100	6 ms	5332 KiB

tree

#include<iostream>
#include<vector>
#define int long long
using namespace std;
int segtree[800001],cnt,n,q;
pair<int,int> range[200001];
vector <int> v[200001];
int dp[200001][19],arr[200001],depth[200001];
void dfs(int node,int dep)
{
    int temp=++cnt;
    depth[node]=dep;
    for(int i=0;i<v[node].size();i++)
        dfs(v[node][i],dep+1);
    range[node]={temp,cnt};
}
void update(int node,int ts,int te,int s,int e,int val)
{
    if(ts>=s&&te<=e)
        segtree[node]=+val;
    else if(ts>e||te<s)
        return;
    else
    {
        int mid=(ts+te)/2;
        update(node*2,ts,mid,s,e,val);
        update(node*2+1,mid+1,te,s,e,val);
    }
}
int get(int node,int ts,int te,int x)
{
    if(ts>x||te<x)
        return -1<<31;
    else if(ts==x&&te==x)
        return segtree[node];
    else
    {
        int mid=(ts+te)/2;
        return max(get(node*2,ts,mid,x),get(node*2+1,mid+1,te,x))+segtree[node];
    }
}
int getnode(int node,int t)
{
    for(int i=18;i>=0;i--)
    {
        if(t>=(1<<i))
        {
            node=dp[node][i];
            t-=(1<<i);
        }
    }
    return node;
}
int lca(int a,int b)
{
    if(depth[a]<depth[b])
        b=getnode(b,depth[b]-depth[a]);
    else
        a=getnode(a,depth[a]-depth[b]);
    int l=0,r=n;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(getnode(a,mid)==getnode(b,mid))
            r=mid;
        else
            l=mid+1;
    }
    return getnode(a,l);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    arr[1]=1;
    for(int i=2;i<=n;i++)
    {
        cin>>arr[i];
        v[arr[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
        dp[i][0]=arr[i];
    for(int i=0;i<18;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[j][i+1]=dp[dp[j][i]][i];
        }
    }
    dfs(1,0);
    while(q--)
    {
        int b,c,d,e;
        cin>>b>>c>>d;
        int t1,t2,t3,t4;
        t1=range[b].first;
        t2=range[b].second;
        t3=range[c].first;
        t4=range[c].second;
        e=lca(b,c);
        if(d==0)
        {
            if(get(1,1,n,range[e].first)==get(1,1,n,t1)&&get(1,1,n,range[e].first)==get(1,1,n,t3))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else
        {
            if(get(1,1,n,t1)==get(1,1,n,range[e].first)&&get(1,1,n,t3)==get(1,1,n,range[e].first))
            {
                cout<<"YES"<<endl;
                update(1,1,n,t1,t2,1);
            }
            else
            {
                cout<<"NO"<<endl;
                update(1,1,n,t3,t4,1);
            }
        }
    }
}

Compilation message (stderr)

tree.cpp: In function 'void dfs(long long int, long long int)':
tree.cpp:13:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<v[node].size();i++)
      |                 ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 14
• Subtask 4: 0 / 19
• Subtask 5: 0 / 45