| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 92571 |
2019-01-03T15:21:05 Z |
ansol4328 |
None (KOI16_tree) |
C++11 |
|
3 ms |
504 KB |
#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(res) T.update_segtree(x,par[x]);
else T.update_segtree(y,par[y]);
}
return 0;
}
Compilation message
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
