답안 #6769 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6769	2014-07-05T18:53:56 Z	cki86201	오두막집 (GA7_cabana)	C++	40 / 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_];
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]);
}

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);
		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 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);
        if(x != i-1)flag = 1;
    }
    for(i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        is[x] = 1;
    }
    if(flag == 0){

    }
    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;
        if(K == 1){
			printf("%d",MIN);
			return 0;
        }
    }
    printf("%d",ans);
    return 0;
}

Subtask #1
7.0 / 7.0

#	결과	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	5116 KB	Output is correct
2	Correct	100 ms	5216 KB	Output is correct
3	Correct	92 ms	5360 KB	Output is correct
4	Correct	428 ms	5904 KB	Output is correct
5	Correct	1592 ms	7672 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

#	결과	메모리	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
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	5116 KB	Output is correct
2	Correct	4 ms	5116 KB	Output is correct
3	Correct	16 ms	5116 KB	Output is correct
4	Correct	148 ms	5116 KB	Output is correct
5	Correct	52 ms	5116 KB	Output is correct
6	Correct	100 ms	5116 KB	Output is correct
7	Correct	140 ms	5512 KB	Output is correct
8	Correct	252 ms	6568 KB	Output is correct
9	Correct	152 ms	5116 KB	Output is correct
10	Correct	232 ms	6304 KB	Output is correct
11	Correct	4 ms	5116 KB	Output is correct
12	Correct	156 ms	5116 KB	Output is correct
13	Correct	496 ms	9472 KB	Output is correct
14	Correct	160 ms	5116 KB	Output is correct
15	Correct	464 ms	9736 KB	Output is correct
16	Correct	112 ms	5116 KB	Output is correct
17	Correct	108 ms	5116 KB	Output is correct

Subtask #5
0.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	5116 KB	Output is correct
2	Correct	116 ms	5116 KB	Output is correct
3	Correct	108 ms	5116 KB	Output is correct
4	Correct	444 ms	5116 KB	Output is correct
5	Correct	1572 ms	5512 KB	Output is correct
6	Execution timed out	6000 ms	7756 KB	Program timed out
7	Halted	0 ms	0 KB	-

답안 #6769

Compilation message

Subtask #1 7.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
7.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