oj.uz

Submission #6056

# Submission time Handle Problem Language Result Execution time Memory
6056 2014-06-15T22:04:51 Z kriii 오두막집 (GA7_cabana) C++
0 / 100
 260 ms 8576 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);
	for (int t=0;t<ad.size();t++){
		int o = c[ad[t]];
		pair<vector<int>, long long> a = over(st==x[ad[t]]?y[ad[t]]:x[ad[t]],dist);
		for (int r=0;r<a.first.size();r++){
			e[last] = a.first[r] + o;
			if (ca[st] && e[last] <= dist) ret.second++;
			last++;
		}
		sz[cnt++] = a.first.size();
		ret.second += a.second;
	}
	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
0.0 / 7.0

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

Subtask #2
0.0 / 23.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8048 KB Output is correct
2 Correct 56 ms 8180 KB Output is correct
3 Incorrect 260 ms 8576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 37.0

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