oj.uz

Submission #6773

# Submission time Handle Problem Language Result Execution time Memory
6773 2014-07-06T04:54:54 Z cki86201 오두막집 (GA7_cabana) C++
33 / 100
 6000 ms 10908 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]);
}

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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 6288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 6288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6288 KB Output is correct
2 Correct 0 ms 6288 KB Output is correct
3 Correct 0 ms 6288 KB Output is correct
4 Correct 0 ms 6288 KB Output is correct
5 Correct 0 ms 6288 KB Output is correct
6 Correct 0 ms 6288 KB Output is correct
7 Correct 0 ms 6288 KB Output is correct
8 Correct 0 ms 6288 KB Output is correct
9 Correct 0 ms 6288 KB Output is correct
10 Correct 0 ms 6288 KB Output is correct

Subtask #4
21.0 / 21.0

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

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