Submission #12814

#	Time	Username	Problem	Language	Result	Execution time	Memory
12814		dohyun0324	오두막집 (GA7_cabana)	C++98	100 / 100	2116 ms	34176 KiB

cabana

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int x,y,top,n,m,w,pos[100010],d[100010],N,mi,ch[100010],cnt,cab[100010];
long long t,k;
int arr[2000010],st[100010],en[100010],arr2[2000010],check[2000010],anc[100010];
int point;
struct data{
    int x,y,c;
    bool operator<(const data&r)const{
        return x<r.x;
    }
}con[200010];
void init(int x)
{
    int i;
    d[x]=0;
    ch[x]=cnt;
    for(i=pos[x];;i++)
    {
        if(x!=con[i].x) break;
        if(ch[con[i].y]==cnt || anc[con[i].y]) continue;
        init(con[i].y);
        d[x]+=d[con[i].y];
    }
    d[x]++;
}
void finding(int x)
{
    int i;
    ch[x]=cnt;
    for(i=pos[x];;i++)
    {
        if(x!=con[i].x) break;
        if(ch[con[i].y]==cnt || anc[con[i].y]) continue;
        if(d[con[i].y]>=N/2)
        {
            finding(con[i].y);
        }
    }
    if(mi==0) mi=x;
}
void dfs(int x,int lev)
{
    int i,j;
    ch[x]=cnt;
    for(i=pos[x];;i++)
    {
        if(x!=con[i].x) break;
        if(ch[con[i].y]==cnt || anc[con[i].y]) continue;
        if(cab[con[i].y]==1){arr[++top]=lev+con[i].c; arr2[top]=arr[top];}
        dfs(con[i].y,lev+con[i].c);
        if(x==mi)
        {
            check[point]=1;
            for(j=point;j<=top;j++) arr2[j]=arr[j];
            sort(arr2+point,arr2+top+1);
            point=top+1;
        }
    }
}
void pro(int x,int mid)
{
    int i,p2; mi=0;
    cnt++; init(x);
    N=d[x]; p2=top+1; point=top+1;
    cnt++; finding(x);
    mid=mi; st[mid]=top+1;
    cnt++; dfs(mid,0);
    if(cab[mid]==1) arr[++top]=0;
    sort(arr+p2,arr+top+1);
    en[mid]=top;
    anc[mid]=1;
    for(i=pos[mid];;i++)
    {
        if(con[i].x!=mid) break;
        if(anc[con[i].y]) continue;
        pro(con[i].y,0);
    }
}
void pro2(int x,int gap,int mid)
{
    int i,j; mi=0;
    if(gap==1)
    {
        gap=1;
    }
    long long dap=0;
    cnt++; init(x);
    N=d[x];
    cnt++; finding(x);
    mid=mi;
    anc[mid]=1;
    int p=en[mid],s=st[mid];
    for(i=st[mid];i<=en[mid];i++)
    {
        while(arr[i]+arr[p]>gap && p>st[mid]-1) p--;
        if(p==st[mid]-1) break;
        dap+=p-st[mid]+1;
    }
    for(i=st[mid]+1;i<=en[mid];i++)
    {
        if(check[i]==1 || i==en[mid]){
            if(check[i]==0 && cab[mid]==0) i++;
            p=i-1;
            for(j=s;j<i;j++)
            {
                while(arr2[j]+arr2[p]>gap && p>s-1) p--;
                if(p==s-1) break;
                dap-=p-s+1;
            }
            s=i;
        }
    }
    dap/=2;
    t+=dap;
    for(i=pos[mid];;i++)
    {
        if(con[i].x!=mid) break;
        if(anc[con[i].y]) continue;
        pro2(con[i].y,gap,0);
    }
}
void bsearch()
{
    int s=1,e=25000000,mid2;
    while(s!=e)
    {
        mid2=(s+e)/2; t=0;
        memset(anc,0,sizeof anc);
        pro2(1,mid2,0);
        if(t<k) s=mid2+1;
        else e=mid2;
    }
    printf("%d",s);
}
int main()
{
    int i;
    scanf("%d %d %lld",&n,&m,&k);
    for(i=2;i<=n;i++)
    {
        scanf("%d %d",&x,&y);
        w++; con[w].x=i; con[w].y=x; con[w].c=y;
        w++; con[w].x=x; con[w].y=i; con[w].c=y;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d",&x);
        cab[x]=1;
    }
    sort(con+1,con+w+1);
    for(i=1;i<=w;i++)
    {
        if(con[i].x!=con[i-1].x) pos[con[i].x]=i;
    }
    pro(1,0);
    bsearch();
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37