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

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;
	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;
}

Subtask #1
7.0 / 7.0

#	Verdict	Memory	Grader output
1	Correct	5116 KB	Output is correct
2	Correct	5116 KB	Output is correct
3	Correct	5116 KB	Output is correct
4	Correct	5116 KB	Output is correct
5	Correct	5116 KB	Output is correct
6	Correct	5116 KB	Output is correct
7	Correct	5116 KB	Output is correct
8	Correct	5116 KB	Output is correct
9	Correct	5116 KB	Output is correct
10	Correct	5116 KB	Output is correct

Subtask #2
0.0 / 23.0

#	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	-

Subtask #3
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	5116 KB	Output is correct
2	Correct	5116 KB	Output is correct
3	Correct	5116 KB	Output is correct
4	Correct	5116 KB	Output is correct
5	Correct	5116 KB	Output is correct
6	Correct	5116 KB	Output is correct
7	Correct	5116 KB	Output is correct
8	Correct	5116 KB	Output is correct
9	Correct	5116 KB	Output is correct
10	Correct	5116 KB	Output is correct

Subtask #4
0.0 / 21.0

#	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	-

Subtask #5
0.0 / 37.0

#	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	-

Submission #6760

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 0.0 / 23.0

Subtask #3 12.0 / 12.0

Subtask #4 0.0 / 21.0

Subtask #5 0.0 / 37.0

Subtask #1
7.0 / 7.0

Subtask #2
0.0 / 23.0

Subtask #3
12.0 / 12.0

Subtask #4
0.0 / 21.0

Subtask #5
0.0 / 37.0