Submission #92572

#	Time	Username	Problem	Language	Result	Execution time	Memory
92572		ansol4328	트리 (KOI16_tree)	C++98	100 / 100	374 ms	47352 KiB

tree

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

struct SegmentTree
{
    vector<bool> tree;
    int base;
    void setup(int a)
    {
        base=1;
        while(base<a) base=base<<1;
        tree.resize(base*2+2,true);
        base--;
    }
    void update(int idx)
    {
        idx+=base;
        tree[idx]=false;
        idx=idx>>1;
        while(idx!=0)
        {
            tree[idx]=(tree[idx*2] && tree[idx*2+1]);
            idx=idx>>1;
        }
    }
    bool pos(int num, int st, int fn, int ns=1, int nf=-1)
    {
        if(nf==-1) nf=base+1;
        if(fn<ns || nf<st) return true;
        if(st<=ns && nf<=fn) return tree[num];
        int mid=(ns+nf)>>1;
        return (pos(num*2,st,fn,ns,mid) && pos(num*2+1,st,fn,mid+1,nf));
    }
};

struct HeavyLightDecomposition
{
    vector<vector<int> > lst;
    vector<int> par, sub, depth;
    vector<int> tail, dfsn, chain;
    vector<SegmentTree> HLDSegTree;
    int dn;
    HeavyLightDecomposition(int a)
    {
        lst.resize(a+2);

        sub.resize(a+2);

        par.resize(a+2);
        depth.resize(a+2);
        dn=0;
        tail.resize(a+2);
        dfsn.resize(a+2);
        chain.resize(a+2);

        HLDSegTree.resize(a+2);
    }
    void add_edge(int v1, int v2)
    {
        lst[v1].push_back(v2);
    }
    void get_subsize(int cur, int prev);
    void HLD(int cur, int prev, int c_num);
    void construct_segtree(int a);
    void update_segtree(int v1, int v2);
    bool linked(int x, int y);
};

void HeavyLightDecomposition::get_subsize(int cur, int prev)
{
    sub[cur]=1;
    for(int i=0 ; i<lst[cur].size() ; i++)
    {
        int nxt=lst[cur][i];
        if(nxt!=prev)
        {
            HeavyLightDecomposition::get_subsize(nxt,cur);
            sub[cur]+=sub[nxt];
        }
    }
}

void HeavyLightDecomposition::HLD(int cur, int prev, int c_num)
{
    dfsn[cur]=++dn;
    chain[dn]=c_num;
    tail[c_num]=dn;
    depth[dfsn[cur]]=depth[dfsn[prev]]+1;
    par[dfsn[cur]]=dfsn[prev];
    int idx=-1;
    for(int i=0 ; i<lst[cur].size() ; i++)
    {
        int nxt=lst[cur][i];
        if(nxt!=prev && (idx==-1 || sub[nxt]>sub[idx])) idx=nxt;
    }
    if(idx!=-1) HeavyLightDecomposition::HLD(idx,cur,c_num);
    for(int i=0 ; i<lst[cur].size() ; i++)
    {
        int nxt=lst[cur][i];
        if(nxt!=prev && nxt!=idx)
            HeavyLightDecomposition::HLD(nxt,cur,dn+1);
    }
}

void HeavyLightDecomposition::construct_segtree(int a)
{
    for(int i=1 ; i<=a ; i++)
    {
        if(chain[dfsn[i]]==dfsn[i]) HLDSegTree[dfsn[i]].setup(tail[dfsn[i]]-dfsn[i]+1);
    }
}

void HeavyLightDecomposition::update_segtree(int v1, int v2)
{
    v1=dfsn[v1], v2=dfsn[v2];
    if(depth[v1]>depth[v2]) swap(v1,v2);
    if(v2==1) return;
    int seg_num=chain[v2];
    if(chain[v1]==chain[v2]) HLDSegTree[seg_num].update(v2-chain[v2]+1);
    else HLDSegTree[seg_num].update(1);
}

bool HeavyLightDecomposition::linked(int x, int y)
{
    bool ret;
    x=dfsn[x];
    y=dfsn[y];
    if(x==y) return true;
    while(chain[x]!=chain[y])
    {
        int x1=chain[x];
        int y1=chain[y];
        if(depth[x1]>depth[y1])
        {
            ret=HLDSegTree[chain[x]].pos(1,1,x-chain[x]+1);
            x=par[x1];
        }
        else
        {
            ret=HLDSegTree[chain[y]].pos(1,1,y-chain[y]+1);
            y=par[y1];
        }
        if(ret==false) return false;
    }
    if(depth[x]>depth[y]) swap(x,y);
    if(x!=y) ret=HLDSegTree[chain[x]].pos(1,x-chain[x]+2,y-chain[x]+1);
    return ret;
}

int main()
{
    int n, m;
    scanf("%d %d",&n,&m);
    vector<int> par(n+2);
    HeavyLightDecomposition T(n);
    par[1]=1;
    for(int i=2 ; i<=n ; i++)
    {
        int x;
        scanf("%d",&x);
        par[i]=x;
        T.add_edge(x,i);
    }
    T.get_subsize(1,0);
    T.HLD(1,0,1);
    T.construct_segtree(n);
    for(int i=0 ; i<m ; i++)
    {
        int x, y, z;
        scanf("%d %d %d",&x,&y,&z);
        bool res=T.linked(x,y);
        printf("%s\n",res ? "YES" : "NO");
        if(z==0) continue;
        if(res) T.update_segtree(x,par[x]);
        else T.update_segtree(y,par[y]);
    }
    return 0;
}

Compilation message (stderr)

tree.cpp: In member function 'void HeavyLightDecomposition::get_subsize(int, int)':
tree.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<lst[cur].size() ; i++)
                   ~^~~~~~~~~~~~~~~~
tree.cpp: In member function 'void HeavyLightDecomposition::HLD(int, int, int)':
tree.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<lst[cur].size() ; i++)
                   ~^~~~~~~~~~~~~~~~
tree.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<lst[cur].size() ; i++)
                   ~^~~~~~~~~~~~~~~~
tree.cpp: In function 'int main()':
tree.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
tree.cpp:164:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
tree.cpp:174:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&x,&y,&z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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