Submission #31990

#	Time	Username	Problem	Language	Result	Execution time	Memory
31990		cki86201	오두막집 (GA7_cabana)	C++11	79 / 100	6000 ms	29736 KiB

cabana

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int N, M;
ll K;
vector <pii> E[100010];
int C[100010];
int down[100010];
int cut[100010];

void pdfs(int x, int fa) {
	down[x] = 1;
	for(pii e : E[x]) if(e.Se != fa && cut[e.Se] == 0) {
		pdfs(e.Se, x);
		down[x] += down[e.Se];
	}
}

void dfs(int x, int fa, int L, vector <int> &v) {
	if(C[x]) v.pb(L);
	for(pii e : E[x]) if(e.Se != fa && cut[e.Se] == 0) {
		dfs(e.Se, x, L + e.Fi, v);
	}
}

ll Get(vector <vector <int> > &X, int L) {
	priority_queue <pii, vector<pii>, greater<pii> > pq;
	int n = sz(X);
	rep(i, n) pq.push(pii(sz(X[i]), i));
	ll res = 0;
	while(sz(pq) > 1) {
		pii a = pq.top(); pq.pop();
		pii b = pq.top(); pq.pop();
		int ia = a.Se, ib = b.Se;
		int La = a.Fi, Lb = b.Fi;
		vector <int> R(La + Lb);
		for(int a=La-1, b=0;a>=0;a--) {
			while(b < Lb && X[ia][a] + X[ib][b] <= L) ++b;
			res += b;
		}
		for(int a=0, b=0, c=0;c<La + Lb;c++) {
			if(a == La || (b < Lb && X[ib][b] <= X[ia][a])) R[c] = X[ib][b++];
			else R[c] = X[ia][a++];
		}
		pq.push(pii(a.Fi + b.Fi, sz(X)));
		X.pb(R);
	}
	return res;
}

ll Do(int x, int L) {
	pdfs(x, -1);
	int h = down[x] / 2;
	while(1) {
		int f = 0;
		for(pii e : E[x]) if(down[x] > down[e.Se] && down[e.Se] > h) {
			x = e.Se; f = 1; break;
		}
		if(f == 0) break;
	}
	vector <vector <int> > P;
	
	if(C[x] == 1) {
		vector <int> v; v.pb(0);
		P.pb(v);
	}
	cut[x] = 1;
	for(pii e : E[x]) if(cut[e.Se] == 0) {
		vector <int> v;
		dfs(e.Se, x, e.Fi, v);
		sort(all(v));
		if(sz(v)) P.pb(v);
	}
	ll res = Get(P, L);
	for(pii e : E[x]) if(cut[e.Se] == 0) res += Do(e.Se, L);
	return res;
}

ll Get(int L) {
	memset(cut, 0, sizeof cut);
	return Do(1, L);
}

void solve(){
	scanf("%d%d%lld", &N, &M, &K);
	for(int i=2;i<=N;i++) {
		int x, y; scanf("%d%d", &x, &y);
		E[i].pb(pii(y, x));
		E[x].pb(pii(y, i));
	}
	rep(i, M) {
		int x; scanf("%d", &x);
		C[x] = 1;
	}
	int low = 1, high = (N-1) * 250, res = -1;
	while(low <= high) {
		int mid = (low + high) >> 1;
		if(Get(mid) >= K) res = mid, high = mid - 1;
		else low = mid + 1;
	}
	printf("%d\n", res);
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d\n", tc);
		solve();
	}
	return 0;
};

Compilation message (stderr)

cabana.cpp: In function 'void solve()':
cabana.cpp:114:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &N, &M, &K);
                               ^
cabana.cpp:116:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^
cabana.cpp:121:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
                         ^

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 12 / 12
• Subtask 4: 0 / 21
• Subtask 5: 37 / 37