oj.uz

Submission #6055

# Submission time Handle Problem Language Result Execution time Memory
6055 2014-06-15T21:54:32 Z kriii 오두막집 (GA7_cabana) C++
42 / 100
 6000 ms 12020 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

int N,M; long long K;
int x[100001],y[100001],c[100001],chk[100001]; bool fb[100001],ca[100001];
vector<int> g[100001];
int q[100001],z[100001],d[100001];

pair<vector<int>, long long> over(int s, int dist)
{
	int n = 0, h = 0;

	q[h] = s; d[h] = 0; h++; chk[s] = s;
	while (n < h){
		int u = q[n], w = d[n]; n++;

		for (int t=0,i;t<g[u].size();t++) if (!fb[i=g[u][t]]){
			int v = (u == x[i]) ? y[i] : x[i];
			if (chk[v] != s){
				q[h] = v; d[h] = (w+c[i]); h++; chk[v] = s;
			}
		}
	}

	int dif = 2*n; int st = q[0];
	for (int i=n-1;i>=0;i--){
		int u = q[i]; z[i] = 1;
		int mx = 0;
		for (int t=0,j;t<g[u].size();t++) if (!fb[j=g[u][t]]){
			int v = (u == x[j]) ? y[j] : x[j];
			if (chk[v] != s){
				z[i] += z[-chk[v]];
				mx = max(mx,z[-chk[v]]);
			}
		}
		mx = max(mx,n-z[i]);
		if (dif > mx) st = u, dif = mx;
		chk[u] = -i;
	}

	pair<vector<int>, long long> ret;
	for (int i=0;i<n;i++) if (ca[q[i]]) ret.first.push_back(d[i]);
	sort(ret.first.begin(),ret.first.end());
	ret.second = 0;

	vector<pair<vector<int>, long long> > a; vector<int> ad;
	for (int t=0,i;t<g[st].size();t++) if (!fb[i=g[st][t]]) fb[i] = 1, ad.push_back(i);
	for (int t=0;t<ad.size();t++) a.push_back(over(st==x[ad[t]]?y[ad[t]]:x[ad[t]],dist));
	for (int t=0;t<a.size();t++){
		int o = c[ad[t]];
		for (int r=0;r<a[t].first.size();r++){
			a[t].first[r] += o;
			if (ca[st] && a[t].first[r] <= dist) ret.second++;
		}
	}
	for (int t=0;t<ad.size();t++) fb[ad[t]] = 0;

	while (a.size() > 1){
		vector<pair<vector<int>, long long> > b;
		for (int k=0;k<a.size();k+=2){
			if (k + 1 == a.size()){b.push_back(a[k]); continue;}
			pair<vector<int>, long long> e;
			e.second = a[k].second + a[k+1].second;
			for (int i=0,j=(int)a[k+1].first.size()-1;i<a[k].first.size();i++){
				while (j >= 0 && a[k].first[i] + a[k+1].first[j] > dist) j--;
				e.second += j + 1;
			}
			int i=0,j=0;
			while (i<a[k].first.size() && j<a[k+1].first.size()){
				if (a[k].first[i] < a[k+1].first[j])
					e.first.push_back(a[k].first[i++]);
				else
					e.first.push_back(a[k+1].first[j++]);
			}
			while (i<a[k].first.size()) e.first.push_back(a[k].first[i++]);
			while (j<a[k+1].first.size()) e.first.push_back(a[k+1].first[j++]);
			b.push_back(e);
		}
		a.clear(); a = b; b.clear();
	}
	if (!a.empty()) ret.second += a[0].second;

	return ret;
}

int main()
{
	scanf ("%d %d %lld",&N,&M,&K);
	for (int i=2;i<=N;i++){
		scanf ("%d %d",&y[i],&c[i]); x[i] = i;
		g[x[i]].push_back(i);
		g[y[i]].push_back(i);
	}
	while (M--){
		int v; scanf ("%d",&v);
		ca[v] = 1;
	}

	int l = 1, r = 250 * N, m, a = -1;
	while (l <= r){
		m = (l + r) / 2;
		if (over(1,m).second >= K){
			r = m - 1;
			a = m;
		}
		else l = m + 1;
	}

	printf ("%d\n",a);

	return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6520 KB Output is correct
2 Correct 80 ms 6652 KB Output is correct
3 Correct 88 ms 6652 KB Output is correct
4 Correct 344 ms 7180 KB Output is correct
5 Correct 1076 ms 8260 KB Output is correct
6 Correct 2568 ms 10232 KB Output is correct
7 Correct 2348 ms 9836 KB Output is correct
8 Correct 3520 ms 11824 KB Output is correct
9 Correct 2552 ms 10268 KB Output is correct
10 Correct 3436 ms 11836 KB Output is correct
11 Correct 3720 ms 11960 KB Output is correct
12 Correct 3592 ms 11996 KB Output is correct
13 Correct 3620 ms 12020 KB Output is correct
14 Correct 3744 ms 12020 KB Output is correct
15 Correct 3748 ms 12020 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6520 KB Output is correct
2 Correct 96 ms 6652 KB Output is correct
3 Correct 380 ms 7048 KB Output is correct
4 Correct 3776 ms 9688 KB Output is correct
5 Correct 1340 ms 8100 KB Output is correct
6 Correct 2576 ms 8896 KB Output is correct
7 Correct 3452 ms 9444 KB Output is correct
8 Correct 5364 ms 10428 KB Output is correct
9 Correct 3848 ms 9688 KB Output is correct
10 Correct 5208 ms 10300 KB Output is correct
11 Correct 116 ms 6780 KB Output is correct
12 Correct 4148 ms 9688 KB Output is correct
13 Execution timed out 6000 ms 11936 KB Program timed out
14 Halted 0 ms 0 KB -

Subtask #5
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6520 KB Output is correct
2 Correct 112 ms 6652 KB Output is correct
3 Correct 128 ms 6780 KB Output is correct
4 Correct 452 ms 7180 KB Output is correct
5 Correct 1436 ms 8340 KB Output is correct
6 Correct 4628 ms 10116 KB Output is correct
7 Correct 3180 ms 9780 KB Output is correct
8 Execution timed out 6000 ms 11784 KB Program timed out
9 Halted 0 ms 0 KB -