제출 #197344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197344		dndhk	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	337 ms	32996 KiB

catinatree

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 200000;

int N, D;
int p[MAX_N+1], lv[MAX_N+1], in[MAX_N+1], out[MAX_N+1], cnt;
vector<int> gp[MAX_N+1];

struct SEG{
	struct NODE{
		int l, r, d;
	};
	vector<NODE> seg;
	int SZ;
	void add(){
		seg.pb({-1, -1, 0});
	}
	void Init(int x){
		SZ = x;
		add();
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e)	return;
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
	}
	void Update(int x, int y){
		update(0, 1, SZ, x, y);
	}
	void update(int idx, int s, int e, int x, int y){
		if(s==e){
			seg[idx].d = y;
			return;
		}
		if(x<=(s+e)/2){
			update(seg[idx].l, s, (s+e)/2, x, y);
		}else{
			update(seg[idx].r, (s+e)/2+1, e, x, y);
		}
		if(seg[seg[idx].l].d==0){
			seg[idx].d = seg[seg[idx].r].d;
		}else if(seg[seg[idx].r].d==0){
			seg[idx].d = seg[seg[idx].l].d;
		}else{
			if(lv[seg[seg[idx].l].d]<lv[seg[seg[idx].r].d]){
				seg[idx].d = seg[seg[idx].l].d;
			}else{
				seg[idx].d = seg[seg[idx].r].d;
			}
		}
	}
	int Calc(int x, int y){
		return calc(0, 1, SZ, x, y);
	}
	int calc(int idx, int s, int e, int x, int y){
		if(x<=s && e<=y){
			return seg[idx].d;
		}else if(x>e || y<s)	return 0;
		int t0 = calc(seg[idx].l, s, (s+e)/2, x, y);
		int t1 = calc(seg[idx].r, (s+e)/2+1, e, x, y);
		if(t0==0)	return t1;
		if(t1==0)	return t0;
		if(lv[t0]<lv[t1])	return t0;
		return t1;
	}
}Seg;

void dfs(int x){
	in[x] = ++cnt;
	for(int i : gp[x]){
		lv[i] = lv[x]+1;
		dfs(i);
	}
	out[x] = cnt;
	while(1){
		int c = Seg.Calc(in[x], out[x]);
		if(c==0){
			Seg.Update(in[x], x);
			return;
		}
		Seg.Update(in[c], 0);
		int c2 = Seg.Calc(in[x], out[x]);
		if(c2==0){
			Seg.Update(in[c], c);
			break;
		}
		if(lv[c]-lv[x]+lv[c2]-lv[x]>=D){
			Seg.Update(in[c], c);
			break;
		}
	}
	int c = Seg.Calc(in[x], out[x]);
	if(lv[c]-lv[x]>=D){
		Seg.Update(in[x], x);
	}
}

int main(){
	scanf("%d%d", &N, &D);
	Seg.Init(N);
	for(int i=2; i<=N; i++){
		scanf("%d", &p[i]);
		p[i]++;
		gp[p[i]].pb(i);
	}
	dfs(1);
	int ans = 0;
	while(1){
		int c = Seg.Calc(in[1], out[1]);
		if(c==0)	break;
		ans++;
		Seg.Update(in[c], 0);
	}
	cout<<ans;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

catinatree.cpp: In function 'int main()':
catinatree.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &D);
  ~~~~~^~~~~~~~~~~~~~~~
catinatree.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[i]);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49