Submission #6059

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
6059	2014-06-16T04:00:28 Z	imsifile	오두막집 (GA7_cabana)	C++	100 / 100	492 ms	24144 KB

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

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

Subtask #2
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	24144 KB	Output is correct
2	Correct	0 ms	24144 KB	Output is correct
3	Correct	4 ms	24144 KB	Output is correct
4	Correct	20 ms	24144 KB	Output is correct
5	Correct	76 ms	24144 KB	Output is correct
6	Correct	272 ms	24144 KB	Output is correct
7	Correct	192 ms	24144 KB	Output is correct
8	Correct	404 ms	24144 KB	Output is correct
9	Correct	208 ms	24144 KB	Output is correct
10	Correct	368 ms	24144 KB	Output is correct
11	Correct	452 ms	24144 KB	Output is correct
12	Correct	468 ms	24144 KB	Output is correct
13	Correct	484 ms	24144 KB	Output is correct
14	Correct	492 ms	24144 KB	Output is correct
15	Correct	492 ms	24144 KB	Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	24144 KB	Output is correct
2	Correct	0 ms	24144 KB	Output is correct
3	Correct	20 ms	24144 KB	Output is correct
4	Correct	196 ms	24144 KB	Output is correct
5	Correct	56 ms	24144 KB	Output is correct
6	Correct	128 ms	24144 KB	Output is correct
7	Correct	180 ms	24144 KB	Output is correct
8	Correct	288 ms	24144 KB	Output is correct
9	Correct	176 ms	24144 KB	Output is correct
10	Correct	268 ms	24144 KB	Output is correct
11	Correct	4 ms	24144 KB	Output is correct
12	Correct	200 ms	24144 KB	Output is correct
13	Correct	420 ms	24144 KB	Output is correct
14	Correct	212 ms	24144 KB	Output is correct
15	Correct	416 ms	24144 KB	Output is correct
16	Correct	108 ms	24144 KB	Output is correct
17	Correct	104 ms	24144 KB	Output is correct

Subtask #5
37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	24144 KB	Output is correct
2	Correct	0 ms	24144 KB	Output is correct
3	Correct	4 ms	24144 KB	Output is correct
4	Correct	24 ms	24144 KB	Output is correct
5	Correct	80 ms	24144 KB	Output is correct
6	Correct	264 ms	24144 KB	Output is correct
7	Correct	184 ms	24144 KB	Output is correct
8	Correct	368 ms	24144 KB	Output is correct
9	Correct	284 ms	24144 KB	Output is correct
10	Correct	328 ms	24144 KB	Output is correct
11	Correct	408 ms	24144 KB	Output is correct
12	Correct	392 ms	24144 KB	Output is correct
13	Correct	444 ms	24144 KB	Output is correct
14	Correct	404 ms	24144 KB	Output is correct
15	Correct	408 ms	24144 KB	Output is correct
16	Correct	420 ms	24144 KB	Output is correct
17	Correct	88 ms	24144 KB	Output is correct
18	Correct	264 ms	24144 KB	Output is correct

Submission #6059

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