Submission #6760

# Submission time Handle Problem Language Result Execution time Memory
6760 2014-07-05T16:31:01 Z cki86201 오두막집 (GA7_cabana) C++
19 / 100
6000 ms 11088 KB
#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;
	if(is[fi])Root = rb_insert(Root, 0);
	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;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 5116 KB Output is correct
2 Correct 0 ms 5116 KB Output is correct
3 Correct 0 ms 5116 KB Output is correct
4 Correct 0 ms 5116 KB Output is correct
5 Correct 0 ms 5116 KB Output is correct
6 Correct 0 ms 5116 KB Output is correct
7 Correct 0 ms 5116 KB Output is correct
8 Correct 0 ms 5116 KB Output is correct
9 Correct 0 ms 5116 KB Output is correct
10 Correct 0 ms 5116 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 32 ms 5116 KB Output is correct
2 Correct 100 ms 5216 KB Output is correct
3 Correct 92 ms 5364 KB Output is correct
4 Correct 428 ms 5908 KB Output is correct
5 Correct 1584 ms 7680 KB Output is correct
6 Execution timed out 6000 ms 11088 KB Program timed out
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 5116 KB Output is correct
2 Correct 0 ms 5116 KB Output is correct
3 Correct 0 ms 5116 KB Output is correct
4 Correct 0 ms 5116 KB Output is correct
5 Correct 0 ms 5116 KB Output is correct
6 Correct 0 ms 5116 KB Output is correct
7 Correct 0 ms 5116 KB Output is correct
8 Correct 0 ms 5116 KB Output is correct
9 Correct 0 ms 5116 KB Output is correct
10 Correct 0 ms 5116 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 12 ms 5116 KB Output is correct
2 Correct 68 ms 5116 KB Output is correct
3 Correct 356 ms 5116 KB Output is correct
4 Correct 3200 ms 5116 KB Output is correct
5 Correct 1052 ms 5116 KB Output is correct
6 Correct 2008 ms 5116 KB Output is correct
7 Correct 2876 ms 5512 KB Output is correct
8 Correct 5716 ms 6568 KB Output is correct
9 Correct 3300 ms 5116 KB Output is correct
10 Correct 5264 ms 6304 KB Output is correct
11 Correct 104 ms 5116 KB Output is correct
12 Correct 3464 ms 5116 KB Output is correct
13 Execution timed out 6000 ms 9468 KB Program timed out
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 24 ms 5116 KB Output is correct
2 Correct 112 ms 5116 KB Output is correct
3 Correct 112 ms 5116 KB Output is correct
4 Correct 440 ms 5116 KB Output is correct
5 Correct 1548 ms 5512 KB Output is correct
6 Execution timed out 6000 ms 7756 KB Program timed out
7 Halted 0 ms 0 KB -