Submission #97485

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
97485	2019-02-16T11:45:41 Z	Retro3014	None (KOI16_tree)	C++17	Compilation error	0 ms	0 KB

tree

#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;
	//cout<<x<<' '<<gtop[group[x]]<<' '<<group[x]<<endl;
	if(gsz[group[x]] < 2 * (size[x] - sum(0, 0, N-1, num[x][0]+1, num[x][1]))){
		gsz[cntg] = gsz[group[x]] - (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[cntg]);
		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]));
		gsz[cntg] = (size[x] - sum(0, 0, N-1, num[x][0]+1, num[x][1]));
		p[x] = 0; gtop[cntg] = x; dfs2(x);
		update(0, 0, N-1, num[x][0], gsz[cntg]);
	}
	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] = N; gtop[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 'void cut(int)':
tree.cpp:94:26: error: reference to 'size' is ambiguous
  if(gsz[group[x]] < 2 * (size[x] - sum(0, 0, N-1, num[x][0]+1, num[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:95:32: error: reference to 'size' is ambiguous
   gsz[cntg] = gsz[group[x]] - (size[x] - sum(0, 0, N-1, num[x][0]+1, num[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:96:20: error: reference to 'size' is ambiguous
   gsz[group[x]] = (size[x] - sum(0, 0, N-1, num[x][0]+1, num[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:100:21: error: reference to 'size' is ambiguous
   gsz[group[x]] -= (size[x] - sum(0, 0, N-1, num[x][0]+1, num[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:101:16: error: reference to 'size' is ambiguous
   gsz[cntg] = (size[x] - sum(0, 0, N-1, num[x][0]+1, num[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: In function 'int main()':
tree.cpp:110: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:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[i]);
   ~~~~~^~~~~~~~~~~~~
tree.cpp:120: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~