oj.uz

Submission #31988

# Submission time Handle Problem Language Result Execution time Memory
31988 2017-09-21T05:56:24 Z cki86201 오두막집 (GA7_cabana) C++11
100 / 100
 5226 ms 22188 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) {
	int n = sz(X);
	ll res = 0;
	for(int i=1;i<n;i<<=1) {
		for(int j=0;j<n;j+=(i<<1)) {
			if(j+i < n) {
				int La = sz(X[j]), Lb = sz(X[j+i]);
				vector <int> R(La + Lb);
				for(int a=La-1, b=0;a>=0;a--) {
					while(b < Lb && X[j][a] + X[j+i][b] <= L) ++b;
					res += b;
				}
				for(int a=0, b=0, c=0;c<La + Lb;c++) {
					if(a == La || (b < Lb && X[j+i][b] <= X[j][a])) R[c] = X[j+i][b++];
					else R[c] = X[j][a++];
				}
				swap(X[j], 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:112: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:114: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:119: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 5536 KB Output is correct
2 Correct 0 ms 5536 KB Output is correct
3 Correct 0 ms 5536 KB Output is correct
4 Correct 3 ms 5536 KB Output is correct
5 Correct 3 ms 5536 KB Output is correct
6 Correct 3 ms 5536 KB Output is correct
7 Correct 3 ms 5536 KB Output is correct
8 Correct 0 ms 5536 KB Output is correct
9 Correct 3 ms 5536 KB Output is correct
10 Correct 0 ms 5536 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5536 KB Output is correct
2 Correct 56 ms 5848 KB Output is correct
3 Correct 56 ms 6172 KB Output is correct
4 Correct 236 ms 7288 KB Output is correct
5 Correct 803 ms 10184 KB Output is correct
6 Correct 2059 ms 13364 KB Output is correct
7 Correct 1756 ms 14020 KB Output is correct
8 Correct 2963 ms 16020 KB Output is correct
9 Correct 1999 ms 15268 KB Output is correct
10 Correct 2829 ms 16132 KB Output is correct
11 Correct 3153 ms 16368 KB Output is correct
12 Correct 3259 ms 16384 KB Output is correct
13 Correct 3069 ms 16428 KB Output is correct
14 Correct 3226 ms 16428 KB Output is correct
15 Correct 3203 ms 16428 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5536 KB Output is correct
2 Correct 46 ms 5800 KB Output is correct
3 Correct 226 ms 6328 KB Output is correct
4 Correct 1859 ms 9232 KB Output is correct
5 Correct 663 ms 7384 KB Output is correct
6 Correct 1193 ms 8308 KB Output is correct
7 Correct 2036 ms 8984 KB Output is correct
8 Correct 2956 ms 9728 KB Output is correct
9 Correct 2076 ms 9232 KB Output is correct
10 Correct 3143 ms 9652 KB Output is correct
11 Correct 66 ms 5800 KB Output is correct
12 Correct 2239 ms 9232 KB Output is correct
13 Correct 5226 ms 11164 KB Output is correct
14 Correct 2616 ms 9364 KB Output is correct
15 Correct 4866 ms 11280 KB Output is correct
16 Correct 2113 ms 9100 KB Output is correct
17 Correct 2123 ms 9100 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5668 KB Output is correct
2 Correct 63 ms 5800 KB Output is correct
3 Correct 73 ms 5800 KB Output is correct
4 Correct 296 ms 6328 KB Output is correct
5 Correct 1119 ms 7532 KB Output is correct
6 Correct 3156 ms 9476 KB Output is correct
7 Correct 2813 ms 9192 KB Output is correct
8 Correct 4075 ms 10596 KB Output is correct
9 Correct 2659 ms 9876 KB Output is correct
10 Correct 4383 ms 10464 KB Output is correct
11 Correct 4389 ms 11160 KB Output is correct
12 Correct 4873 ms 10852 KB Output is correct
13 Correct 4556 ms 11676 KB Output is correct
14 Correct 5106 ms 10872 KB Output is correct
15 Correct 4999 ms 11252 KB Output is correct
16 Correct 2999 ms 16260 KB Output is correct
17 Correct 1333 ms 22188 KB Output is correct
18 Correct 2153 ms 13148 KB Output is correct