Submission #97818

#	Time	Username	Problem	Language	Result	Execution time	Memory
97818		Retro3014	트리 (KOI16_tree)	C++17	100 / 100	1315 ms	44496 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_M = 200000;

int N, M;
vector<int> gp[MAX_N+1];
int num[MAX_N+1][2];
int lv[MAX_N+1];
int cnt = -1;
int p[MAX_N+1][20];

struct SEG{
	SEG (int l, int r, int mx, int lazy) : l(l), r(r), mx(mx), lazy(lazy) {}
	int l, r, mx, lazy;
};

vector<SEG> seg;

void init(int idx, int s, int e){
	seg.push_back({-1, -1, 1, 0});
	if(s==e)	return;
	seg[idx].l = seg.size(); init(seg[idx].l, s, (s+e)/2);
	seg[idx].r = seg.size(); init(seg[idx].r, (s+e)/2+1, e);
}

void lazy2(int idx, int s, int e, int x, int y, int lz){
	if(idx==-1)	return;
	if(x<=s && e<=y){
		seg[idx].lazy = max(lz, seg[idx].lazy); seg[idx].mx = max(seg[idx].mx, lz);
		return;
	}if(x>e || y<s)	return;
	lazy2(seg[idx].l, s, (s+e)/2, x, y, lz);
	lazy2(seg[idx].r, (s+e)/2+1, e, x, y, lz);
}

void lazy(int x, int y, int z){
	lazy2(0, 0, N-1, x, y, z);
}

int find2(int idx, int s, int e, int k){
	if(seg[idx].lazy!=0){
		if(seg[idx].l!=-1){
			seg[seg[idx].l].mx = max(seg[seg[idx].l].mx, seg[idx].lazy); seg[seg[idx].l].lazy = max(seg[seg[idx].l].lazy, seg[idx].lazy);
		}if(seg[idx].r!=-1){
			seg[seg[idx].r].mx = max(seg[seg[idx].r].mx, seg[idx].lazy); seg[seg[idx].r].lazy = max(seg[seg[idx].r].lazy, seg[idx].lazy);
		}seg[idx].lazy = 0;
	}
	if(s==e)	return seg[idx].mx;
	if(k<=(s+e)/2)	return find2(seg[idx].l, s, (s+e)/2, k);
	else	return find2(seg[idx].r, (s+e)/2+1, e, k);
}

int find(int x){
	return find2(0, 0, N-1, x);
}

int up(int x, int y){
	for(int k=19; k>=0; k--){
		if(lv[p[x][k]]>=y)	x = p[x][k];
	}
	return x;
}


void dfs(int x){
	for(int k=1; k<20; k++)	p[x][k] = p[p[x][k-1]][k-1];
	num[x][0] = ++cnt;
	lv[x] = lv[p[x][0]]+1;
	for(auto i : gp[x])	dfs(i);
	num[x][1] = cnt;
}

bool query(int x, int y){
	int lx = find(num[x][0]), ly = find(num[y][0]);
	x = up(x, lx), y = up(y, ly);
	if(x==y)	return true;
	return false;
}

void cut(int x){
	lazy(num[x][0], num[x][1], lv[x]);
}

int main(){
	scanf("%d%d", &N, &M);
	init(0, 0, N-1);
	for(int i=2; i<=N; i++){
		scanf("%d", &p[i][0]); gp[p[i][0]].pb(i);
	}
	dfs(1);
	for(int i=0; i<M; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		bool tf = query(a, b);
		if(tf){
			printf("YES\n");
			if(c)	cut(a);
		}else{
			printf("NO\n");
			if(c)	cut(b);
		}
	}
	return 0;
}

Compilation message (stderr)

tree.cpp: In function 'int main()':
tree.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
tree.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[i][0]); gp[p[i][0]].pb(i);
   ~~~~~^~~~~~~~~~~~~~~~
tree.cpp:115: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: 19 / 19
• Subtask 5: 45 / 45