Submission #6053

#	Time	Username	Problem	Language	Result	Execution time	Memory
6053		kriii	오두막집 (GA7_cabana)	C++98	0 / 100	6000 ms	9684 KiB

cabana

#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 = N*2; vector<pair<int, int> > cut; int st;
	for (int i=n-1;i>=0;i--){
		int u = q[i]; z[i] = 1;
		vector<pair<int, int> > gath;
		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]];
				gath.push_back(make_pair(z[-chk[v]],j));
			}
			else gath.push_back(make_pair(n-z[-chk[v]]-1,j));
		}
		sort(gath.begin(),gath.end());
		int ndif = 0;
		for (int i=0;i<gath.size();i++) ndif += gath[i].first * ((i % 2) * 2 - 1);
		if (dif > abs(ndif)){
			st = u;
			dif = abs(ndif);
			cut = gath;
		}
		gath.clear();
		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;
	if (n > 1){
		pair<vector<int>, long long> a,b; int e,o;
		if (cut.size() > 1){
			for (int i=0;i<cut.size();i++) if (i % 2) fb[cut[i].second] = 1;
			a = over(st,dist);
			for (int i=0;i<cut.size();i++) fb[cut[i].second] = !fb[cut[i].second];
			b = over(st,dist);
			for (int i=0;i<cut.size();i++) fb[cut[i].second] = 0;
			e = ca[st]; o = 0;
		}
		else{
			fb[cut[0].second] = 1;
			a = over(x[cut[0].second],dist);
			b = over(y[cut[0].second],dist);
			fb[cut[0].second] = 0;
			e = 0; o = c[cut[0].second];
		}

		ret.second = a.second + b.second;
		for (int i=e,j=(int)b.first.size()-1;i<a.first.size();i++){
			while (j >= 0 && a.first[i] + o + b.first[j] > dist) j--;
			ret.second += j + 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;
	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 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37