| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 97478 |
2019-02-16T11:26:19 Z |
Retro3014 |
None (KOI16_tree) |
C++17 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 200000;
const int MAX_Q = 200000;
int N, Q;
vector<int> gp[MAX_N+1];
int p[MAX_N+1];
int num[MAX_N+1][2];
int cnt = 0;
int size[MAX_N+1];
struct SEG{
SEG(int l, int r, int sum) : l(l), r(r), sum(sum) {}
int l, r, sum;
};
vector<SEG> seg;
void init(){
seg.push_back({-1, -1, 0});
}
void update(int idx, int s, int e, int x, int y){
seg[idx].sum+=y;
if(s==e) return;
if(x<=(s+e)/2){
if(seg[idx].l==-1){
seg[idx].l = seg.size();
}update(seg[idx].l, s, (s+e)/2, x, y);
}else{
if(seg[idx].r==-1){
seg[idx].r = seg.size();
}update(seg[idx].r, (s+e)/2+1, e, x, y);
}
}
int sum(int idx, int s, int e, int x, int y){
if(idx==-1) return 0;
if(x<=s && e<=y) return seg[idx].sum;
if(x>e || y<s) return 0;
return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
}
void dfs(int x){
size[x] = 1;
num[x][0] = cnt++;
for(auto i : gp[x]){
dfs(i);
size[x] += size[i];
}
num[x][1] = cnt;
}
int group[MAX_N+1];
int gsz[MAX_N+1];
int gtop[MAX_N+1];
int cntg = 2;
void dfs2(int x){
group[x] = cntg;
for(auto i : gp[x]){
if(p[i]!=x) continue;
dfs2(i);
}
}
void cut(int x){
if(p[x]==0) return;/*
if(gsz[group[x]] < 2 * (size[x] - sum(0, 0, N-1, num[x][0]+1, num[x][1]))){
gsz[group[x]] = (size[x] - sum(0, 0, N-1, num[x][0]+1, num[x][1]));
p[x] = 0; gtop[cntg] = gtop[group[x]]; dfs2(gtop[group[x]]);
gtop[group[x]] = x; update(0, 0, N-1, num[x][0], gsz[group[x]]);
}else{
gsz[group[x]] -= (size[x] - sum(0, 0, N-1, num[x][0]+1, num[x][1]));
p[x] = 0; gtop[cntg] = x; p[x] = 0; dfs2(x);
gsz[group[x]] = (size[x] - sum(0, 0, N-1, num[x][0]+1, num[x][1]));
update(0, 0, N-1, num[x][0], gsz[group[x]]);
}*/
p[x] = 0; dfs2(x);
cntg++;
}
int main(){
init();
scanf("%d%d", &N, &Q);
for(int i=2; i<=N; i++){
scanf("%d", &p[i]);
gp[p[i]].pb(i);
}
dfs(1);
for(int i=1; i<=N; i++) group[i] = 1;
gsz[1] = 1;
rep(q, Q){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(group[a]==group[b]) printf("YES\n");
else printf("NO\n");
if(c==1){
if(group[a]==group[b]) cut(a);
else cut(b);
}
}
return 0;
}
Compilation message
tree.cpp: In function 'void dfs(int)':
tree.cpp:68:2: error: reference to 'size' is ambiguous
size[x] = 1;
^~~~
tree.cpp:32:5: note: candidates are: int size [200001]
int size[MAX_N+1];
^~~~
In file included from /usr/include/c++/7/string:51:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from tree.cpp:1:
/usr/include/c++/7/bits/range_access.h:252:5: note: template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])
size(const _Tp (&/*__array*/)[_Nm]) noexcept
^~~~
/usr/include/c++/7/bits/range_access.h:242:5: note: template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)
size(const _Container& __cont) noexcept(noexcept(__cont.size()))
^~~~
tree.cpp:72:3: error: reference to 'size' is ambiguous
size[x] += size[i];
^~~~
tree.cpp:32:5: note: candidates are: int size [200001]
int size[MAX_N+1];
^~~~
In file included from /usr/include/c++/7/string:51:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from tree.cpp:1:
/usr/include/c++/7/bits/range_access.h:252:5: note: template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])
size(const _Tp (&/*__array*/)[_Nm]) noexcept
^~~~
/usr/include/c++/7/bits/range_access.h:242:5: note: template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)
size(const _Container& __cont) noexcept(noexcept(__cont.size()))
^~~~
tree.cpp:72:14: error: reference to 'size' is ambiguous
size[x] += size[i];
^~~~
tree.cpp:32:5: note: candidates are: int size [200001]
int size[MAX_N+1];
^~~~
In file included from /usr/include/c++/7/string:51:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from tree.cpp:1:
/usr/include/c++/7/bits/range_access.h:252:5: note: template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])
size(const _Tp (&/*__array*/)[_Nm]) noexcept
^~~~
/usr/include/c++/7/bits/range_access.h:242:5: note: template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)
size(const _Container& __cont) noexcept(noexcept(__cont.size()))
^~~~
tree.cpp: In function 'int main()':
tree.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~
tree.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p[i]);
~~~~~^~~~~~~~~~~~~
tree.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
