Submission #6059

#	Time	Username	Problem	Language	Result	Execution time	Memory
6059		imsifile	오두막집 (GA7_cabana)	C++98	100 / 100	492 ms	24144 KiB

cabana

#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(i=0; i<pcn; i++)txt[tcn][0]=dst[su[i]], txt[tcn++][1]=who[su[i]];
	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, j, k;
	for(i=0; i<cal; i++){
		if(lng[i]==lng[i+1])continue;
		for(j=lng[i]; j<lng[i+1]; j++)gas[txt[j][1]]++, sum++;
		for(k=lng[i+1]-1, j=lng[i];; j++){
			gas[txt[j][1]]--, sum--;
			for(; k>j; k--){
				if(txt[j][0]+txt[k][0]<=dist)break;
				gas[txt[k][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);
	countpair(5);
	while(1){
		mid=(mi+mx)/2, cnt=0;
		if(mi>=mx)break;
		countpair(mid); // 거리가 mid 이하인 쌍의 개수를 구함
		if(cnt<k)mi=mid+1;
		else mx=mid;
	}
	printf("%d", mid);
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37