oj.uz

Submission #31990

# Submission time Handle Problem Language Result Execution time Memory
31990 2017-09-21T06:08:04 Z cki86201 오두막집 (GA7_cabana) C++11
79 / 100
 6000 ms 29736 KB 
#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

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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5540 KB Output is correct
2 Correct 59 ms 5852 KB Output is correct
3 Correct 59 ms 6176 KB Output is correct
4 Correct 276 ms 7292 KB Output is correct
5 Correct 903 ms 10220 KB Output is correct
6 Correct 2533 ms 13592 KB Output is correct
7 Correct 2096 ms 14212 KB Output is correct
8 Correct 3673 ms 16368 KB Output is correct
9 Correct 2366 ms 15464 KB Output is correct
10 Correct 3406 ms 16504 KB Output is correct
11 Correct 3913 ms 16784 KB Output is correct
12 Correct 3933 ms 16908 KB Output is correct
13 Correct 3823 ms 16824 KB Output is correct
14 Correct 3886 ms 16824 KB Output is correct
15 Correct 3696 ms 16820 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5540 KB Output is correct
2 Correct 49 ms 5804 KB Output is correct
3 Correct 249 ms 6332 KB Output is correct
4 Correct 2169 ms 9236 KB Output is correct
5 Correct 709 ms 7388 KB Output is correct
6 Correct 1396 ms 8312 KB Output is correct
7 Correct 2003 ms 8992 KB Output is correct
8 Correct 3906 ms 9892 KB Output is correct
9 Correct 2416 ms 9236 KB Output is correct
10 Correct 3383 ms 9860 KB Output is correct
11 Correct 63 ms 5804 KB Output is correct
12 Correct 2816 ms 9368 KB Output is correct
13 Execution timed out 6000 ms 11352 KB Execution timed out
14 Halted 0 ms 0 KB -

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5672 KB Output is correct
2 Correct 66 ms 5804 KB Output is correct
3 Correct 63 ms 5804 KB Output is correct
4 Correct 303 ms 6332 KB Output is correct
5 Correct 1189 ms 7532 KB Output is correct
6 Correct 3339 ms 9532 KB Output is correct
7 Correct 3013 ms 9340 KB Output is correct
8 Correct 4543 ms 11232 KB Output is correct
9 Correct 2929 ms 9968 KB Output is correct
10 Correct 4519 ms 10784 KB Output is correct
11 Correct 5229 ms 11680 KB Output is correct
12 Correct 5803 ms 11080 KB Output is correct
13 Correct 5666 ms 11684 KB Output is correct
14 Correct 5956 ms 11188 KB Output is correct
15 Correct 5316 ms 11720 KB Output is correct
16 Correct 3503 ms 16600 KB Output is correct
17 Correct 2389 ms 29736 KB Output is correct
18 Correct 2483 ms 13552 KB Output is correct