Submission #5945

#	Time	Username	Problem	Language	Result	Execution time	Memory
5945		model_code	오두막집 (GA7_cabana)	C++98	100 / 100	3688 ms	16724 KiB

cabana

#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;
}

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