oj.uz

Submission #6037

# Submission time Handle Problem Language Result Execution time Memory
6037 2014-06-15T19:26:55 Z ainta 오두막집 (GA7_cabana) C++
100 / 100
 616 ms 45980 KB 
#pragma warning(disable:4996)
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>E[100010], L[100010];
vector<int>P[100010];
struct Seg{
	int L, num;
	bool operator < (const Seg &p)const{
		return L < p.L;
	}
};
vector<Seg>w[100010];
int n, m, D[100010], L2[100010], Q[100010], par[100010], sz;
bool chk[100010], House[100010];
long long K;
void BFS(int a){
	int h = 0, t = 0, i, x;
	par[a] = 0;
	Q[++t] = a, D[a] = 1, L2[a] = 0;
	while (h < t){
		x = Q[++h];
		for (i = 0; i < E[x].size(); i++){
			if (!D[E[x][i]] && !chk[E[x][i]]){
				D[E[x][i]] = 1;
				Q[++t] = E[x][i];
				L2[E[x][i]] = L2[x] + L[x][i];
				par[E[x][i]] = x;
			}
		}
	}
	sz = t;
}
int GetMid(int a){
	int i, x;
	BFS(a);
	for (i = sz; i >= 1; i--){
		x = Q[i];
		D[par[x]] += D[x];
		if (D[x] > sz / 2){
			break;
		}
	}
	for (i = 1; i <= sz; i++)D[Q[i]] = 0;
	return x;
}
void Do(int a)
{
	int Mid = GetMid(a);
	if (sz == 1){
		if (House[a])P[a].push_back(0);
		return;
	}
	int i, x, j;
	Seg tp;
	chk[Mid] = true;
	for (i = 0; i < E[Mid].size(); i++){
		x = E[Mid][i];
		if (!chk[x]){
			Do(x);
			for (j = 0; j < P[x].size(); j++){
				tp.L = P[x][j] + L[Mid][i];
				tp.num = x;
				w[Mid].push_back(tp);
			}
			P[x].clear();
		}
	}
	if (House[Mid]){
		tp.L = 0, tp.num = Mid;
		w[Mid].push_back(tp);
	}
	if (!w[Mid].empty()){
		sort(w[Mid].begin(), w[Mid].end());
	}
	chk[Mid] = false;
	BFS(a);
	for (i = 1; i <= sz; i++){
		D[Q[i]] = 0;
		if (House[Q[i]])P[a].push_back(L2[Q[i]]);
	}
}
int cnt[100010];
long long Gap(int Len)
{
	int i, pv, j, sz;
	long long S = 0;
	for (i = 1; i <= n; i++){
		if (w[i].empty())continue;
		pv = -1;
		sz = w[i].size();
		for (j = sz - 1; j >= 0; j--){
			while (pv + 1 < sz && w[i][pv + 1].L + w[i][j].L <= Len){
				pv++;
				cnt[w[i][pv].num]++;
			}
			S += pv + 1 - cnt[w[i][j].num];
		}
		for (j = 0; j <= pv; j++)cnt[w[i][j].num]--;
	}
	return S;
}
int main(){
	int i, a, b, be, ed, mid, Res;
	scanf("%d%d%lld", &n, &m, &K);
	for (i = 2; i <= n; i++){
		scanf("%d%d", &a, &b);
		E[a].push_back(i);
		E[i].push_back(a);
		L[a].push_back(b);
		L[i].push_back(b);
	}
	for (i = 0; i < m; i++){
		scanf("%d", &a);
		House[a] = true;
	}
	Do(1);
	be = 1, ed = 250 * (n - 1);
	while (be <= ed){
		mid = (be + ed) >> 1;
		if (Gap(mid) >= K * 2){
			Res = mid;
			ed = mid - 1;
		}
		else{
			be = mid + 1;
		}
	}
	printf("%d\n", Res);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12736 KB Output is correct
2 Correct 0 ms 12736 KB Output is correct
3 Correct 4 ms 12736 KB Output is correct
4 Correct 0 ms 12736 KB Output is correct
5 Correct 0 ms 12736 KB Output is correct
6 Correct 0 ms 12736 KB Output is correct
7 Correct 0 ms 12736 KB Output is correct
8 Correct 0 ms 12736 KB Output is correct
9 Correct 0 ms 12736 KB Output is correct
10 Correct 4 ms 12736 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12868 KB Output is correct
2 Correct 4 ms 13268 KB Output is correct
3 Correct 8 ms 13264 KB Output is correct
4 Correct 32 ms 14716 KB Output is correct
5 Correct 100 ms 19180 KB Output is correct
6 Correct 288 ms 33960 KB Output is correct
7 Correct 208 ms 26636 KB Output is correct
8 Correct 476 ms 42316 KB Output is correct
9 Correct 228 ms 27532 KB Output is correct
10 Correct 428 ms 39972 KB Output is correct
11 Correct 496 ms 45536 KB Output is correct
12 Correct 524 ms 45752 KB Output is correct
13 Correct 516 ms 45980 KB Output is correct
14 Correct 520 ms 45980 KB Output is correct
15 Correct 528 ms 45980 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12736 KB Output is correct
2 Correct 0 ms 12736 KB Output is correct
3 Correct 0 ms 12736 KB Output is correct
4 Correct 0 ms 12736 KB Output is correct
5 Correct 0 ms 12736 KB Output is correct
6 Correct 0 ms 12736 KB Output is correct
7 Correct 0 ms 12736 KB Output is correct
8 Correct 0 ms 12736 KB Output is correct
9 Correct 0 ms 12736 KB Output is correct
10 Correct 0 ms 12736 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12736 KB Output is correct
2 Correct 4 ms 13132 KB Output is correct
3 Correct 28 ms 14056 KB Output is correct
4 Correct 252 ms 19204 KB Output is correct
5 Correct 100 ms 15904 KB Output is correct
6 Correct 164 ms 17752 KB Output is correct
7 Correct 228 ms 20160 KB Output is correct
8 Correct 356 ms 24820 KB Output is correct
9 Correct 240 ms 19204 KB Output is correct
10 Correct 336 ms 24240 KB Output is correct
11 Correct 4 ms 13264 KB Output is correct
12 Correct 260 ms 19336 KB Output is correct
13 Correct 572 ms 36140 KB Output is correct
14 Correct 264 ms 19336 KB Output is correct
15 Correct 556 ms 35348 KB Output is correct
16 Correct 116 ms 18940 KB Output is correct
17 Correct 136 ms 19072 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12868 KB Output is correct
2 Correct 4 ms 13132 KB Output is correct
3 Correct 8 ms 13264 KB Output is correct
4 Correct 24 ms 14464 KB Output is correct
5 Correct 108 ms 18504 KB Output is correct
6 Correct 376 ms 27316 KB Output is correct
7 Correct 212 ms 24808 KB Output is correct
8 Correct 532 ms 33572 KB Output is correct
9 Correct 356 ms 24320 KB Output is correct
10 Correct 412 ms 36296 KB Output is correct
11 Correct 552 ms 34900 KB Output is correct
12 Correct 496 ms 40748 KB Output is correct
13 Correct 616 ms 35532 KB Output is correct
14 Correct 504 ms 41528 KB Output is correct
15 Correct 616 ms 35688 KB Output is correct
16 Correct 468 ms 42276 KB Output is correct
17 Correct 84 ms 25196 KB Output is correct
18 Correct 320 ms 33824 KB Output is correct