oj.uz

Submission #12813

# Submission time Handle Problem Language Result Execution time Memory
12813 2015-01-04T16:52:02 Z dohyun0324 오두막집 (GA7_cabana) C++
40 / 100
 2132 ms 34172 KB 
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int x,y,top,n,m,k,w,pos[100010],d[100010],N,mi,ch[100010],cnt,cab[100010];
long long t;
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 %d",&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
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29608 KB Output is correct
2 Correct 40 ms 29712 KB Output is correct
3 Correct 64 ms 29856 KB Output is correct
4 Correct 188 ms 30400 KB Output is correct
5 Correct 528 ms 31772 KB Output is correct
6 Correct 1004 ms 32940 KB Output is correct
7 Correct 1080 ms 33540 KB Output is correct
8 Correct 1428 ms 34056 KB Output is correct
9 Correct 1248 ms 34172 KB Output is correct
10 Correct 1408 ms 34168 KB Output is correct
11 Incorrect 1456 ms 34172 KB Output isn't correct
12 Halted 0 ms 0 KB -

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 204 ms 29608 KB Output is correct
4 Correct 1556 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 1316 ms 29608 KB Output is correct
8 Correct 1812 ms 29608 KB Output is correct
9 Correct 1564 ms 29608 KB Output is correct
10 Correct 1808 ms 29608 KB Output is correct
11 Correct 64 ms 29608 KB Output is correct
12 Correct 1696 ms 29608 KB Output is correct
13 Correct 2132 ms 29608 KB Output is correct
14 Correct 1716 ms 29608 KB Output is correct
15 Correct 1992 ms 29608 KB Output is correct
16 Correct 1212 ms 29608 KB Output is correct
17 Correct 1216 ms 29608 KB Output is correct

Subtask #5
0.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 224 ms 29608 KB Output is correct
5 Correct 584 ms 29608 KB Output is correct
6 Correct 1364 ms 29608 KB Output is correct
7 Correct 1160 ms 29608 KB Output is correct
8 Correct 1960 ms 29608 KB Output is correct
9 Correct 1840 ms 29608 KB Output is correct
10 Incorrect 1572 ms 29608 KB Output isn't correct
11 Halted 0 ms 0 KB -