답안 #5945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5945 2014-06-05T14:02:45 Z model_code 오두막집 (GA7_cabana) C++
100 / 100
3688 ms 16724 KB
#include<stdio.h>
#include<memory.h>
#include<algorithm>
using namespace std;

typedef long long lld;

int n, m, cab[100100], chk[100100], root[100100], cal;
int txt[2000000], 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;
	if(root[cal])return root[cal];
	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;
	}
	root[cal]=st;
	return st;
}

void dfs(int dist, int st){ // 다른 subtree 간의 쌍 개수
	int s, e, i, mx=0;
	par[st]=0, ix[st]=top[st], dst[st]=0;
	stk[scn++]=st, pcn=0;
	while(scn){
		s=stk[scn-1];
		if(ix[s]==-1){
			if(cab[s] && s!=st)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]]);
			if(cab[st] && cab[e] && dst[e]<=dist)cnt++;
			stk[scn++]=e;
		}
		ix[s]=prv[ix[s]];
	}
	if(lng[cal+1]<0){
		sort(su, su+pcn, comp);
		for(e=0; e<pcn; e++)txt[tcn++]=su[e];
		lng[cal+1]=tcn;
	}
	else{
		for(e=0; e<pcn; e++)su[e]=txt[e+lng[cal]];
	}
	if(!pcn)return;
	for(e=0; e<pcn; e++)gas[who[su[e]]]++, sum++;
	for(s=0, e=pcn-1;; s++){
		gas[who[su[s]]]--, sum--;
		for(; e>s; e--){
			if(dst[su[s]]+dst[su[e]]<=dist)break;
			gas[who[su[e]]]--, sum--;
		}
		if(s>=e)break;
		cnt+=sum-gas[who[su[s]]];
	}
}

void countpair(int dist, int st){
	int i;
	st=findroot(st), dfs(dist, st), cal++;
	chk[st]=1;
	for(i=top[st]; i>=0; i=prv[i]){
		if(chk[endp[i]])continue;
		countpair(dist, endp[i]);
	}
}

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;
	while(1){
		mid=(mi+mx)/2, cal=cnt=0;
		if(mi>=mx)break;
		memset(chk, 0, sizeof(chk));
		countpair(mid, 1); // 거리가 mid 이하인 쌍의 개수를 구함
		if(cnt<k)mi=mid+1;
		else mx=mid;
	}
	printf("%d", mid);
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 16724 KB Output is correct
2 Correct 0 ms 16724 KB Output is correct
3 Correct 0 ms 16724 KB Output is correct
4 Correct 0 ms 16724 KB Output is correct
5 Correct 0 ms 16724 KB Output is correct
6 Correct 0 ms 16724 KB Output is correct
7 Correct 0 ms 16724 KB Output is correct
8 Correct 0 ms 16724 KB Output is correct
9 Correct 0 ms 16724 KB Output is correct
10 Correct 0 ms 16724 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 16724 KB Output is correct
2 Correct 24 ms 16724 KB Output is correct
3 Correct 36 ms 16724 KB Output is correct
4 Correct 140 ms 16724 KB Output is correct
5 Correct 432 ms 16724 KB Output is correct
6 Correct 912 ms 16724 KB Output is correct
7 Correct 916 ms 16724 KB Output is correct
8 Correct 1264 ms 16724 KB Output is correct
9 Correct 1076 ms 16724 KB Output is correct
10 Correct 1292 ms 16724 KB Output is correct
11 Correct 1272 ms 16724 KB Output is correct
12 Correct 1272 ms 16724 KB Output is correct
13 Correct 1176 ms 16724 KB Output is correct
14 Correct 1228 ms 16724 KB Output is correct
15 Correct 1192 ms 16724 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 16724 KB Output is correct
2 Correct 0 ms 16724 KB Output is correct
3 Correct 0 ms 16724 KB Output is correct
4 Correct 0 ms 16724 KB Output is correct
5 Correct 0 ms 16724 KB Output is correct
6 Correct 0 ms 16724 KB Output is correct
7 Correct 0 ms 16724 KB Output is correct
8 Correct 0 ms 16724 KB Output is correct
9 Correct 0 ms 16724 KB Output is correct
10 Correct 0 ms 16724 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16724 KB Output is correct
2 Correct 32 ms 16724 KB Output is correct
3 Correct 168 ms 16724 KB Output is correct
4 Correct 2760 ms 16724 KB Output is correct
5 Correct 684 ms 16724 KB Output is correct
6 Correct 1756 ms 16724 KB Output is correct
7 Correct 2232 ms 16724 KB Output is correct
8 Correct 3156 ms 16724 KB Output is correct
9 Correct 2732 ms 16724 KB Output is correct
10 Correct 3156 ms 16724 KB Output is correct
11 Correct 52 ms 16724 KB Output is correct
12 Correct 2984 ms 16724 KB Output is correct
13 Correct 3688 ms 16724 KB Output is correct
14 Correct 3076 ms 16724 KB Output is correct
15 Correct 3364 ms 16724 KB Output is correct
16 Correct 1104 ms 16724 KB Output is correct
17 Correct 1136 ms 16724 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16724 KB Output is correct
2 Correct 36 ms 16724 KB Output is correct
3 Correct 48 ms 16724 KB Output is correct
4 Correct 176 ms 16724 KB Output is correct
5 Correct 528 ms 16724 KB Output is correct
6 Correct 2068 ms 16724 KB Output is correct
7 Correct 1132 ms 16724 KB Output is correct
8 Correct 3128 ms 16724 KB Output is correct
9 Correct 3188 ms 16724 KB Output is correct
10 Correct 1576 ms 16724 KB Output is correct
11 Correct 3412 ms 16724 KB Output is correct
12 Correct 1556 ms 16724 KB Output is correct
13 Correct 3460 ms 16724 KB Output is correct
14 Correct 1492 ms 16724 KB Output is correct
15 Correct 3476 ms 16724 KB Output is correct
16 Correct 1308 ms 16724 KB Output is correct
17 Correct 200 ms 16724 KB Output is correct
18 Correct 864 ms 16724 KB Output is correct