Submission #5945

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
5945	2014-06-05T14:02:45 Z	model_code	오두막집 (GA7_cabana)	C++	100 / 100	3688 ms	16724 KB

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.0 / 7.0

#	Verdict	Memory	Grader output
1	Correct	16724 KB	Output is correct
2	Correct	16724 KB	Output is correct
3	Correct	16724 KB	Output is correct
4	Correct	16724 KB	Output is correct
5	Correct	16724 KB	Output is correct
6	Correct	16724 KB	Output is correct
7	Correct	16724 KB	Output is correct
8	Correct	16724 KB	Output is correct
9	Correct	16724 KB	Output is correct
10	Correct	16724 KB	Output is correct

Subtask #2
23.0 / 23.0

#	Verdict	Execution time	Memory	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

Subtask #3
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	16724 KB	Output is correct
2	Correct	16724 KB	Output is correct
3	Correct	16724 KB	Output is correct
4	Correct	16724 KB	Output is correct
5	Correct	16724 KB	Output is correct
6	Correct	16724 KB	Output is correct
7	Correct	16724 KB	Output is correct
8	Correct	16724 KB	Output is correct
9	Correct	16724 KB	Output is correct
10	Correct	16724 KB	Output is correct

Subtask #4
21.0 / 21.0

#	Verdict	Execution time	Memory	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

Subtask #5
37.0 / 37.0

#	Verdict	Execution time	Memory	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

Submission #5945

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 23.0 / 23.0

Subtask #3 12.0 / 12.0

Subtask #4 21.0 / 21.0

Subtask #5 37.0 / 37.0

Subtask #1
7.0 / 7.0

Subtask #2
23.0 / 23.0

Subtask #3
12.0 / 12.0

Subtask #4
21.0 / 21.0

Subtask #5
37.0 / 37.0