| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 6058 |
2014-06-16T03:47:56 Z |
imsifile |
오두막집 (GA7_cabana) |
C++ |
|
0 ms |
24144 KB |
#include<stdio.h>
#include<memory.h>
#include<algorithm>
using namespace std;
typedef long long lld;
int n, m, cab[100100], chk[100100], cal;
int txt[2000000][2], tcn, lng[100100];
int mi=1, mx, mid;
int top[100100], endp[200200], val[200200], prv[200200], ecn;
int par[100100], subtr[100100], dst[100100], who[100100];
int stk[100100], ix[100100], scn;
int su[100100], pcn;
lld k, cnt, gas[100100], sum;
bool comp(const int& x, const int& y){
return dst[x]<dst[y];
}
void edge(int s, int e, int v){
endp[ecn]=e, val[ecn]=v, prv[ecn]=top[s], top[s]=ecn++;
}
int findroot(int st){
int s, e, gas, gap, i;
par[st]=0, ix[st]=top[st], subtr[st]=1;
stk[scn++]=st;
while(scn){
s=stk[scn-1];
if(ix[s]==-1){
if(par[s])subtr[par[s]]+=subtr[s];
scn--;
continue;
}
e=endp[ix[s]];
if(!chk[e] && e!=par[s]){
par[e]=s, ix[e]=top[e], subtr[e]=1;
stk[scn++]=e;
}
ix[s]=prv[ix[s]];
}
gas=subtr[st];
while(1){
gap=gas-1;
for(i=top[st]; i>=0; i=prv[i]){
e=endp[i];
if(chk[e] || e==par[st])continue;
if(subtr[e] > gas/2)break;
gap-=subtr[e];
}
if(i>=0)st=e;
else if(gap > gas/2)st=par[st];
else break;
}
return st;
}
void dfs(int st){ // 다른 subtree 간의 쌍 개수
int s, e, i, mx=0;
par[st]=0, ix[st]=top[st], dst[st]=0, who[st]=st;
stk[scn++]=st, pcn=0;
while(scn){
s=stk[scn-1];
if(ix[s]==-1){
if(cab[s])su[pcn++]=s;
scn--;
continue;
}
e=endp[ix[s]];
if(!chk[e] && e!=par[s]){
par[e]=s, ix[e]=top[e], dst[e]=dst[s]+val[ix[s]];
if(mx<dst[e])mx=dst[e];
who[e]=(s==st?e:who[par[e]]);
stk[scn++]=e;
}
ix[s]=prv[ix[s]];
}
sort(su, su+pcn, comp);
for(e=0; e<pcn; e++)txt[tcn][0]=dst[su[s]], txt[tcn++][1]=who[su[e]];
lng[cal+1]=tcn;
}
void precount(int st){
int i;
st=findroot(st), dfs(st), cal++;
chk[st]=1;
for(i=top[st]; i>=0; i=prv[i]){
if(chk[endp[i]])continue;
precount(endp[i]);
}
}
void countpair(int dist){
int i, js=0, j, k;
for(i=0; i<cal; i++){
if(!lng[i])continue;
for(j=js; j<js+lng[i]; j++)gas[txt[j][1]]++, sum++;
for(k=j-1, j=js;; j++){
gas[txt[j][1]]--, sum--;
for(; k>j; k--){
if(txt[j][0]+txt[k][0]<=dist)break;
gas[txt[j][1]]--, sum--;
}
if(j>=k)break;
cnt+=sum-gas[txt[j][1]];
}
}
}
int main(){
int i, p, v;
scanf("%d%d%lld", &n, &m, &k), mx=250*n;
for(i=1; i<=n; i++)top[i]=-1;
memset(lng, -1, sizeof(lng)), lng[0]=0;
for(i=2; i<=n; i++){
scanf("%d%d", &p, &v);
edge(i, p, v), edge(p, i, v);
}
for(i=0; i<m; i++)scanf("%d", &p), cab[p]=1;
precount(1);
while(1){
mid=(mi+mx)/2, cal=cnt=0;
if(mi>=mx)break;
memset(chk, 0, sizeof(chk));
countpair(mid); // 거리가 mid 이하인 쌍의 개수를 구함
if(cnt<k)mi=mid+1;
else mx=mid;
}
printf("%d", mid);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
24144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
24144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
24144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
24144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
24144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
