oj.uz

답안 #6058

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6058 2014-06-16T03:47:56 Z imsifile 오두막집 (GA7_cabana) C++
0 / 100
 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;
}

Subtask #1
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 24144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 24144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 24144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 24144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 24144 KB Output isn't correct
2 Halted 0 ms 0 KB -