답안 #6773 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6773	2014-07-06T04:54:54 Z	cki86201	오두막집 (GA7_cabana)	C++	33 / 100	6000 ms	10908 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_];
int MIN = 1e8;

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 min_ele(node *root)
{
	if(!root->link[0])return root->data;
	return min_ele(root->link[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);
		if(Root)MIN = min(MIN, L + min_ele(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 flag = 0;
int q1[N_], q2[N_];
int LL[N_];
int top1, top2;

ll lower2(int x, int L, int H)
{
	if(L == H)return 0;
	int m = (L+H)>>1;
	int i, cnt = 0;
	top1 = top2 = 0;
	for(i=m;i>=L;i--){
		if(is[i])q1[top1++] = cnt;
		cnt += LL[i];
	}
	cnt = 0;
	for(i=m+1;i<=H;i++){
		cnt += LL[i];
		if(is[i])q2[top2++] = cnt;
	}
	int j = 0;
	ll ans = 0;
	for(i=0;i<top1;i++){
		while(j != top2 && q2[j] + q1[i] <= x)++j;
		ans += j;
	}
	return ans + lower2(x, L, m) + lower2(x, m+1, H);
}

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);
        LL[i] = y;
        addE(i, x, y, i<<1);
        addE(x, i, y, i<<1|1);
        if(x != i-1)flag = 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(flag){
        if(lower(mid) >= K)ans = mid, high = mid - 1;
        else low = mid + 1;
        if(K == 1){
			printf("%d",MIN);
			return 0;
        }
        }
        else{
			if(lower2(mid, 1, n) >= K)ans = mid, high = mid - 1;
			else low = mid + 1;
        }
    }
    printf("%d",ans);
    return 0;
}

Subtask #1
0.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	6288 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	6288 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
12.0 / 12.0

#	결과	메모리	Grader output
1	Correct	6288 KB	Output is correct
2	Correct	6288 KB	Output is correct
3	Correct	6288 KB	Output is correct
4	Correct	6288 KB	Output is correct
5	Correct	6288 KB	Output is correct
6	Correct	6288 KB	Output is correct
7	Correct	6288 KB	Output is correct
8	Correct	6288 KB	Output is correct
9	Correct	6288 KB	Output is correct
10	Correct	6288 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6288 KB	Output is correct
2	Correct	4 ms	6288 KB	Output is correct
3	Correct	20 ms	6288 KB	Output is correct
4	Correct	144 ms	6288 KB	Output is correct
5	Correct	56 ms	6288 KB	Output is correct
6	Correct	96 ms	6288 KB	Output is correct
7	Correct	140 ms	6684 KB	Output is correct
8	Correct	268 ms	7740 KB	Output is correct
9	Correct	148 ms	6288 KB	Output is correct
10	Correct	240 ms	7476 KB	Output is correct
11	Correct	4 ms	6288 KB	Output is correct
12	Correct	156 ms	6288 KB	Output is correct
13	Correct	520 ms	10644 KB	Output is correct
14	Correct	172 ms	6288 KB	Output is correct
15	Correct	484 ms	10908 KB	Output is correct
16	Correct	108 ms	6288 KB	Output is correct
17	Correct	104 ms	6288 KB	Output is correct

Subtask #5
0.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	6288 KB	Output is correct
2	Correct	116 ms	6288 KB	Output is correct
3	Correct	108 ms	6288 KB	Output is correct
4	Correct	440 ms	6288 KB	Output is correct
5	Correct	1560 ms	6684 KB	Output is correct
6	Execution timed out	6000 ms	8924 KB	Program timed out
7	Halted	0 ms	0 KB	-

답안 #6773

Compilation message

Subtask #1 0.0 / 7.0

Subtask #2 0.0 / 23.0

Subtask #3 12.0 / 12.0

Subtask #4 21.0 / 21.0

Subtask #5 0.0 / 37.0

Subtask #1
0.0 / 7.0

Subtask #2
0.0 / 23.0

Subtask #3
12.0 / 12.0

Subtask #4
21.0 / 21.0

Subtask #5
0.0 / 37.0