Submission #97486

#	Time	Username	Problem	Language	Result	Execution time	Memory
97486		Retro3014	트리 (KOI16_tree)	C++11	36 / 100	2073 ms	25592 KiB

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 (stderr)

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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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