oj.uz

Submission #12814

# Submission time Handle Problem Language Result Execution time Memory
12814 2015-01-04T16:54:51 Z dohyun0324 오두막집 (GA7_cabana) C++
100 / 100
 2116 ms 34176 KB 
#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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29608 KB Output is correct
2 Correct 40 ms 29708 KB Output is correct
3 Correct 68 ms 29860 KB Output is correct
4 Correct 188 ms 30400 KB Output is correct
5 Correct 528 ms 31776 KB Output is correct
6 Correct 1012 ms 32940 KB Output is correct
7 Correct 1076 ms 33536 KB Output is correct
8 Correct 1436 ms 34056 KB Output is correct
9 Correct 1260 ms 34168 KB Output is correct
10 Correct 1412 ms 34168 KB Output is correct
11 Correct 1492 ms 34176 KB Output is correct
12 Correct 1532 ms 34168 KB Output is correct
13 Correct 1424 ms 34172 KB Output is correct
14 Correct 1476 ms 34168 KB Output is correct
15 Correct 1412 ms 34172 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29608 KB Output is correct
2 Correct 40 ms 29608 KB Output is correct
3 Correct 212 ms 29608 KB Output is correct
4 Correct 1536 ms 29608 KB Output is correct
5 Correct 604 ms 29608 KB Output is correct
6 Correct 1116 ms 29608 KB Output is correct
7 Correct 1344 ms 29608 KB Output is correct
8 Correct 1808 ms 29608 KB Output is correct
9 Correct 1556 ms 29608 KB Output is correct
10 Correct 1812 ms 29608 KB Output is correct
11 Correct 68 ms 29608 KB Output is correct
12 Correct 1684 ms 29608 KB Output is correct
13 Correct 2116 ms 29608 KB Output is correct
14 Correct 1756 ms 29608 KB Output is correct
15 Correct 1968 ms 29608 KB Output is correct
16 Correct 1208 ms 29608 KB Output is correct
17 Correct 1208 ms 29608 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29608 KB Output is correct
2 Correct 52 ms 29608 KB Output is correct
3 Correct 72 ms 29608 KB Output is correct
4 Correct 220 ms 29608 KB Output is correct
5 Correct 580 ms 29608 KB Output is correct
6 Correct 1376 ms 29608 KB Output is correct
7 Correct 1160 ms 29608 KB Output is correct
8 Correct 1956 ms 29608 KB Output is correct
9 Correct 1800 ms 29608 KB Output is correct
10 Correct 1580 ms 29608 KB Output is correct
11 Correct 2012 ms 29608 KB Output is correct
12 Correct 1680 ms 29608 KB Output is correct
13 Correct 2072 ms 29608 KB Output is correct
14 Correct 1620 ms 29608 KB Output is correct
15 Correct 2052 ms 29608 KB Output is correct
16 Correct 1464 ms 34172 KB Output is correct
17 Correct 192 ms 29608 KB Output is correct
18 Correct 1016 ms 31828 KB Output is correct