제출 #6773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6773		cki86201	오두막집 (GA7_cabana)	C++98	33 / 100	6000 ms	10908 KiB

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 / 7
• Subtask 2: 0 / 23
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 0 / 37