oj.uz

Submission #6032

# Submission time Handle Problem Language Result Execution time Memory
6032 2014-06-15T18:59:25 Z ainta 오두막집 (GA7_cabana) C++
33 / 100
 2336 ms 65536 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;
	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] >= n / 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].resize(0);
		}
	}
	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
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 12736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16300 KB Output is correct
2 Correct 356 ms 32680 KB Output is correct
3 Correct 512 ms 17276 KB Output is correct
4 Memory limit exceeded 1252 ms 65536 KB Memory limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12736 KB Output is correct
2 Correct 4 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 8 ms 13132 KB Output is correct
3 Correct 24 ms 14188 KB Output is correct
4 Correct 264 ms 19204 KB Output is correct
5 Correct 96 ms 16036 KB Output is correct
6 Correct 196 ms 17888 KB Output is correct
7 Correct 252 ms 20688 KB Output is correct
8 Correct 404 ms 26748 KB Output is correct
9 Correct 260 ms 19204 KB Output is correct
10 Correct 388 ms 25768 KB Output is correct
11 Correct 8 ms 13264 KB Output is correct
12 Correct 296 ms 19468 KB Output is correct
13 Correct 688 ms 40228 KB Output is correct
14 Correct 292 ms 19468 KB Output is correct
15 Correct 684 ms 40492 KB Output is correct
16 Correct 2336 ms 19072 KB Output is correct
17 Correct 2228 ms 19600 KB Output is correct

Subtask #5
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12868 KB Output is correct
2 Correct 108 ms 16564 KB Output is correct
3 Correct 4 ms 13264 KB Output is correct
4 Correct 44 ms 14600 KB Output is correct
5 Memory limit exceeded 1124 ms 65536 KB Memory limit exceeded
6 Halted 0 ms 0 KB -