oj.uz

Submission #6769

# Submission time Handle Problem Language Result Execution time Memory
6769 2014-07-05T18:53:56 Z cki86201 오두막집 (GA7_cabana) C++
40 / 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_];
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

# 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

Subtask #2
0.0 / 23.0

# Verdict Execution time Memory 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

# 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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -