oj.uz

Submission #6057

# Submission time Handle Problem Language Result Execution time Memory
6057 2014-06-15T22:06:41 Z kriii 오두막집 (GA7_cabana) C++
42 / 100
 6000 ms 12900 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],e[100001],f[100001],sz[100001],sp[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<int> ad; int last=0,cnt=0;
	for (int t=0,i;t<g[st].size();t++) if (!fb[i=g[st][t]]) fb[i] = 1, ad.push_back(i);
	vector<pair<vector<int>, long long> > a;
	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<ad.size();t++){
		int o = c[ad[t]];
		for (int r=0;r<a[t].first.size();r++){
			e[last] = a[t].first[r] + o;
			if (ca[st] && e[last] <= dist) ret.second++;
			last++;
		}
		sz[cnt++] = a[t].first.size();
		ret.second += a[t].second;
	} a.clear();
	for (int i=1;i<cnt;i++) sp[i] = sz[i-1] + sp[i-1];
	for (int t=0;t<ad.size();t++) fb[ad[t]] = 0;

	while (cnt > 1){
		int ncnt=0;
		for (int k=0;k<cnt;k+=2){
			if (k + 1 == cnt){sz[ncnt++] = sz[k]; break;}

			for (int i=0,j=sz[k+1]-1;i<sz[k];i++){
				while (j >= 0 && e[i+sp[k]] + e[j+sp[k+1]] > dist) j--;
				ret.second += j + 1;
			}
			int i=0,j=0,p=0;
			while (i<sz[k] && j<sz[k+1]){
				if (e[sp[k]+i] < e[sp[k+1]+j])
					f[p++] = e[sp[k]+i++];
				else
					f[p++] = e[sp[k+1]+j++];
			}
			while (i<sz[k]) f[p++] = e[sp[k]+i++];
			while (j<sz[k+1]) f[p++] = e[sp[k+1]+j++];
			sz[ncnt] = sz[k] + sz[k+1];
			for (int p=0;p<sz[ncnt];p++) e[sp[k] + p] = f[p];
			ncnt++;
		}
		cnt = ncnt;
		for (int i=1;i<cnt;i++) sp[i] = sz[i-1] + sp[i-1];
	}

	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 8080 KB Output is correct
2 Correct 0 ms 8080 KB Output is correct
3 Correct 0 ms 8080 KB Output is correct
4 Correct 0 ms 8080 KB Output is correct
5 Correct 0 ms 8080 KB Output is correct
6 Correct 0 ms 8080 KB Output is correct
7 Correct 0 ms 8080 KB Output is correct
8 Correct 0 ms 8080 KB Output is correct
9 Correct 0 ms 8080 KB Output is correct
10 Correct 0 ms 8080 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8080 KB Output is correct
2 Correct 68 ms 8212 KB Output is correct
3 Correct 84 ms 8212 KB Output is correct
4 Correct 292 ms 8608 KB Output is correct
5 Correct 936 ms 9764 KB Output is correct
6 Correct 2096 ms 11280 KB Output is correct
7 Correct 2000 ms 11176 KB Output is correct
8 Correct 2952 ms 12548 KB Output is correct
9 Correct 2196 ms 11588 KB Output is correct
10 Correct 2864 ms 12636 KB Output is correct
11 Correct 3072 ms 12648 KB Output is correct
12 Correct 2980 ms 12852 KB Output is correct
13 Correct 2948 ms 12872 KB Output is correct
14 Correct 3068 ms 12872 KB Output is correct
15 Correct 3080 ms 12872 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8080 KB Output is correct
2 Correct 72 ms 8212 KB Output is correct
3 Correct 320 ms 8608 KB Output is correct
4 Correct 3744 ms 11248 KB Output is correct
5 Correct 1256 ms 9660 KB Output is correct
6 Correct 2432 ms 10456 KB Output is correct
7 Correct 3100 ms 11008 KB Output is correct
8 Correct 4712 ms 11620 KB Output is correct
9 Correct 3744 ms 11248 KB Output is correct
10 Correct 4516 ms 11588 KB Output is correct
11 Correct 108 ms 8340 KB Output is correct
12 Correct 3960 ms 11248 KB Output is correct
13 Execution timed out 6000 ms 12900 KB Program timed out
14 Halted 0 ms 0 KB -

Subtask #5
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8080 KB Output is correct
2 Correct 92 ms 8212 KB Output is correct
3 Correct 112 ms 8340 KB Output is correct
4 Correct 376 ms 8740 KB Output is correct
5 Correct 1200 ms 9776 KB Output is correct
6 Correct 3844 ms 11264 KB Output is correct
7 Correct 2676 ms 11192 KB Output is correct
8 Correct 5604 ms 12512 KB Output is correct
9 Correct 4636 ms 11580 KB Output is correct
10 Correct 4456 ms 12528 KB Output is correct
11 Correct 5832 ms 12592 KB Output is correct
12 Correct 4992 ms 12728 KB Output is correct
13 Execution timed out 6000 ms 12748 KB Program timed out
14 Halted 0 ms 0 KB -