Submission #6759

#	Time	Username	Problem	Language	Result	Execution time	Memory
6759		cki86201	오두막집 (GA7_cabana)	C++98	0 / 100	32 ms	5116 KiB

cabana

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<ctype.h>
using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> Pi;
#define is_red(x) ((x) && ((x)->red==1))

const int N_ = 100010;
int n, m;
ll K;
int st[N_], en[N_<<1], nxt[N_<<1], len[N_<<1];
inline void addE(int s,int e,int l,int c){nxt[c]=st[s],st[s]=c,en[c]=e,len[c]=l;}
int is[N_], down[N_];
int cut[N_];

struct node{
	node(){}
	node(int data,int sz):data(data),red(1),sz(sz){link[0]=link[1]=0;}
	int red, data, sz;
	node *link[2];
}*Root;

inline int get_size(node *tr){return tr?tr->sz:0;}
inline void update(node *tr){tr->sz = get_size(tr->link[0]) + get_size(tr->link[1]) + 1;}

node *rotate1(node *root,int dir)
{
	node *save = root->link[!dir];
	root->link[!dir] = save->link[dir];
	save->link[dir] = root;
	root->red = 1;
	save->red = 0;
	update(root);
	update(save);
	return save;
}

node *rotate2(node *root,int dir)
{
	root->link[!dir] = rotate1(root->link[!dir],!dir);
	return rotate1(root,dir);
}

node *rb_insert(node *root,int data)
{
	if(!root)root = new node(data, 1);
	else{
		int dir = root->data < data;
		root->link[dir] = rb_insert(root->link[dir],data);
		update(root);
		if(is_red(root->link[dir])){
			if(is_red(root->link[!dir])){
				root->red = 1;
				root->link[0]->red = root->link[1]->red = 0;
			}
			else{
				if(is_red(root->link[dir]->link[dir]))root = rotate1(root,!dir);
				else if(is_red(root->link[dir]->link[!dir]))root = rotate2(root,!dir);
			}
		}
	}
	return root;
}

int count_(int k,node *root){
	if(!root)return 0;
	int dir = root->data <= k;
	if(dir)return get_size(root->link[0]) + 1 + count_(k,root->link[1]);
	else return count_(k,root->link[0]);
}

void remove_memory(node* &root)
{
	if(!root)return;
	remove_memory(root->link[0]);
	remove_memory(root->link[1]);
	free(root);
}

int Assert(node *root)
{
	int lh,rh;
	if(!root)return 1;
	node *ln = root -> link[0];
	node *rn = root -> link[1];
	if(is_red(root)){
		if(is_red(ln)||is_red(rn)){
			puts("Red violation");
			return 0;
		}
	}
	lh = Assert(ln), rh = Assert(rn);
	if((ln && ln->data > root->data) || (rn && rn->data < root->data)){
		puts("Binary tree violation");
		return 0;
	}
	if(lh && rh && lh!=rh){
		puts("Black violation");
		return 0;
	}
	if(lh && rh)return is_red(root)?lh:lh+1;
	return 0;
}

void dfs(int x,int fa)
{
	down[x] = 1;
	for(int i=st[x];i;i=nxt[i]){
		if(en[i] == fa || cut[en[i]])continue;
		dfs(en[i], x);
		down[x] += down[en[i]];
	}
}

int find_mid(int x)
{
	int mid = down[x]/2, i;
	for(;;){
		for(i=st[x];i;i=nxt[i]){
			if(cut[en[i]] || down[en[i]] > down[x])continue;
			if(down[en[i]] > mid){x = en[i];break;}
		}
		if(!i)break;
	}
	return x;
}

void Insert_dfs(int x,int fa,int L)
{
	if(is[x])Root = rb_insert(Root, L);
	for(int i=st[x];i;i=nxt[i]){
		if(en[i] == fa || cut[en[i]])continue;
		Insert_dfs(en[i], x, L + len[i]);
	}
}

ll Find_dfs(int x,int fa,int L,int k)
{
	ll res = 0;
	if(is[x])res += count_(k - L, Root);
	for(int i=st[x];i;i=nxt[i]){
		if(en[i] == fa || cut[en[i]])continue;
		res += Find_dfs(en[i], x, L + len[i], k);
	}
	return res;
}

ll solve(int x,int k)
{
	dfs(x, -1);
	if(down[x] <= 1)return 0;
	int fi = find_mid(x);
	ll res = 0;
	cut[fi] = 1;
	for(int i=st[fi];i;i=nxt[i]){
		if(cut[en[i]])continue;
		res += Find_dfs(en[i],-1,len[i],k);
		Insert_dfs(en[i],-1,len[i]);
	}
	remove_memory(Root); Root = 0;
	for(int i=st[fi];i;i=nxt[i]){
		if(cut[en[i]])continue;
		res += solve(en[i], k);
	}
	return res;
}

ll lower(int x)
{
	memset(cut, 0, sizeof cut);
	return solve(1, x);
}

int main()
{
	scanf("%d%d%lld",&n,&m,&K);
	int i;
	for(i=2;i<=n;i++){
		int x, y;
		scanf("%d%d",&x,&y);
		addE(i, x, y, i<<1);
		addE(x, i, y, i<<1|1);
	}
	for(i=1;i<=m;i++){
		int x;
		scanf("%d",&x);
		is[x] = 1;
	}
	int low = 1, high = 250 * 100000 + 5, mid, ans;
	while(low <= high){
		mid = (low + high) >> 1;
		if(lower(mid) >= K)ans = mid, high = mid - 1;
		else low = mid + 1;
	}
	printf("%d",ans);
	return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37