| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 653652 |
2022-10-27T14:22:26 Z |
Kaang |
None (KOI16_tree) |
C++17 |
|
6 ms |
5332 KB |
#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
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++)
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
