| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12811 |
2015-01-04T16:24:08 Z |
dohyun0324 |
오두막집 (GA7_cabana) |
C++ |
|
56 ms |
29608 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>0) p--;
if(p==0) 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>0) p--;
if(p==0) 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
29608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
29608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
0 ms |
29608 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
29608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
29608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
