oj.uz

Submission #6045

# Submission time Handle Problem Language Result Execution time Memory
6045 2014-06-15T20:47:26 Z kriii 오두막집 (GA7_cabana) C++
19 / 100
 916 ms 65536 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];

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

	q.push_back(s); d.push_back(0); chk[s] = s;
	while (n < q.size()){
		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.push_back(v); d.push_back(w+c[i]); chk[v] = s;
			}
		}
	}

	z.resize(n); long long opp = 0; int cut = -1;
	for (int i=n-1;i>=0;i--){
		int u = q[i]; z[i] = 1;
		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]];
				if (opp < (long long) n * (n - z[-chk[v]])){
					opp = (long long) n * (n - z[-chk[v]]);
					cut = j;
				}
			}
		}
		chk[u] = -i;
	}
	long long cnt = 0;
	if (cut != -1){
		fb[cut] = 1;
		pair<vector<int>, long long> a = over(x[cut],dist);
		pair<vector<int>, long long> b = over(y[cut],dist);
		cnt = a.second + b.second;
		for (int i=0,j=(int)b.first.size()-1;i<a.first.size();i++){
			while (j >= 0 && a.first[i] + c[cut] + b.first[j] > dist) j--;
			cnt += j + 1;
		}
		fb[cut] = 0;
	}

	vector<int> ret;
	for (int i=0;i<n;i++) if (ca[q[i]]) ret.push_back(d[i]);
	sort(ret.begin(),ret.end());
	return make_pair(ret,cnt);
}

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

Subtask #2
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 12824 KB Output is correct
2 Memory limit exceeded 104 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

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

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 12816 KB Output is correct
2 Memory limit exceeded 220 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 12816 KB Output is correct
2 Memory limit exceeded 164 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -