Submission #78353

#	Time	Username	Problem	Language	Result	Execution time	Memory
78353		ansol4328	트리 (KOI16_tree)	C++98	100 / 100	668 ms	41416 KiB

tree

#include<stdio.h>
#include<memory.h>
#include<vector>
#include<algorithm>
#define SIZE 524288
 
using namespace std;
 
struct seg_tree
{
    int limit[SIZE+2], base;
    void setup(int a)
    {
        base=1;
        while(base<a) base*=2;
        for(int i=1 ; i<=base*2 ; i++) limit[i]=1;
        base--;
    }
    void propagate(int ns, int nf, int num)
    {
        if(limit[num]!=1)
        {
            if(ns<nf)
            {
                limit[num*2]=max(limit[num*2],limit[num]);
                limit[num*2+1]=max(limit[num*2+1],limit[num]);
            }
        }
    }
    int get_limit(int st, int fn, int ns, int nf, int num)
    {
        propagate(ns,nf,num);
        if(ns>fn || nf<st) return 1;
        if(st<=ns && nf<=fn) return limit[num];
        int mid=(ns+nf)/2;
        return max(get_limit(st,fn,ns,mid,num*2),get_limit(st,fn,mid+1,nf,num*2+1));
    }
    void update(int st ,int fn, int ns, int nf, int num, int val)
    {
        propagate(ns,nf,num);
        if(ns>fn || nf<st) return;
        if(st<=ns && nf<=fn)
        {
            limit[num]=max(limit[num],val);
            propagate(ns,nf,num);
            return;
        }
        int mid=(ns+nf)/2;
        update(st,fn,ns,mid,num*2,val);
        update(st,fn,mid+1,nf,num*2+1,val);
    }
};
 
int n, qn;
vector<vector<int> > lst;
int depth[200002], par[200002][18];
int dfsn[200002], cnt, enode[200002]; // dfs-order renumbering
seg_tree T;
 
void dfs(int v, int d)
{
    dfsn[v]=++cnt;
    depth[v]=d;
    for(int i=0 ; i<lst[v].size() ; i++)
    {
        int nxt=lst[v][i];
        if(!depth[nxt])
        {
            par[nxt][0]=v;
            dfs(nxt,d+1);
        }
    }
    enode[v]=cnt;
}
 
bool pos(int b, int c)
{
    if(depth[b]<depth[c]) swap(b,c);
    int gap=depth[b]-depth[c], idx=0;
    while(gap!=0)
    {
        if(gap%2==1)
        {
            int limit=T.get_limit(dfsn[b],dfsn[b],1,T.base+1,1);
            b=par[b][idx];
            if(limit>depth[b]) return false;
        }
        gap/=2, idx++;
    }
    if(b==c) return true;
    for(int i=17 ; i>=0 ; i--)
    {
        if(par[b][i]!=par[c][i])
        {
            int limit_b=T.get_limit(dfsn[b],dfsn[b],1,T.base+1,1);
            b=par[b][i];
            int limit_c=T.get_limit(dfsn[c],dfsn[c],1,T.base+1,1);
            c=par[c][i];
            if(limit_b>depth[b] || limit_c>depth[c]) return false;
        }
    }
    int limit_b=T.get_limit(dfsn[b],dfsn[b],1,T.base+1,1);
    b=par[b][0];
    int limit_c=T.get_limit(dfsn[c],dfsn[c],1,T.base+1,1);
    c=par[c][0];
    if(limit_b>depth[b] || limit_c>depth[c]) return false;
    return true;
}
 
int main()
{
    scanf("%d %d",&n,&qn);
    lst.resize(n+1);
    for(int i=2 ; i<=n ; i++)
    {
        int x;
        scanf("%d",&x);
        lst[x].push_back(i);
        lst[i].push_back(x);
    }
    T.setup(n);
    memset(par,-1,sizeof(par));
    dfs(1,1);
    for(int i=1 ; i<=n ; i++) lst[i].clear();
    lst.resize(0);
    for(int j=1 ; j<18 ; j++)
    {
        for(int i=1 ; i<=n ; i++) if(par[i][j-1]!=-1) par[i][j]=par[par[i][j-1]][j-1];
    }
    for(int i=0 ; i<qn ; i++)
    {
        int b, c, d;
        scanf("%d %d %d",&b,&c,&d);
        bool tf=pos(b,c);
        printf("%s\n",tf ? "YES" : "NO");
        if(d==1)
        {
            if(tf) T.update(dfsn[b],enode[b],1,T.base+1,1,depth[b]);
            else T.update(dfsn[c],enode[c],1,T.base+1,1,depth[c]);
        }
    }
    return 0;
}

Compilation message (stderr)

tree.cpp: In function 'void dfs(int, int)':
tree.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<lst[v].size() ; i++)
                   ~^~~~~~~~~~~~~~
tree.cpp: In function 'int main()':
tree.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&qn);
     ~~~~~^~~~~~~~~~~~~~~~
tree.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
tree.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&b,&c,&d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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