oj.uz

Submission #6031

# Submission time Handle Problem Language Result Execution time Memory
6031 2014-06-15T18:57:29 Z ainta 오두막집 (GA7_cabana) C++
33 / 100
 2328 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].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
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 352 ms 32680 KB Output is correct
3 Correct 504 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 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 4 ms 12736 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12736 KB Output is correct
2 Correct 8 ms 13132 KB Output is correct
3 Correct 32 ms 14188 KB Output is correct
4 Correct 256 ms 19204 KB Output is correct
5 Correct 100 ms 16036 KB Output is correct
6 Correct 184 ms 17888 KB Output is correct
7 Correct 232 ms 20688 KB Output is correct
8 Correct 404 ms 26748 KB Output is correct
9 Correct 248 ms 19204 KB Output is correct
10 Correct 380 ms 25768 KB Output is correct
11 Correct 8 ms 13264 KB Output is correct
12 Correct 288 ms 19468 KB Output is correct
13 Correct 668 ms 40228 KB Output is correct
14 Correct 284 ms 19468 KB Output is correct
15 Correct 672 ms 40492 KB Output is correct
16 Correct 2328 ms 19072 KB Output is correct
17 Correct 2192 ms 19600 KB Output is correct

Subtask #5
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 36 ms 14600 KB Output is correct
5 Memory limit exceeded 1152 ms 65536 KB Memory limit exceeded
6 Halted 0 ms 0 KB -