oj.uz

Submission #20881

# Submission time Handle Problem Language Result Execution time Memory
20881 2017-03-03T06:04:37 Z kdh9949 오두막집 (GA7_cabana) C++14
100 / 100
 5426 ms 17184 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct E{ int x, c; };

int n, m, chk[100010], s[100010], vis[100010];
vector<E> e[100010];
vector<int> av, cv[100010];
ll K;

int sd(int x, int p){
	if(vis[x]) return 0;
	s[x] = 1;
	for(auto &i : e[x]) if(i.x != p) s[x] += sd(i.x, x);
	return s[x];
}

int cd(int x, int p, int n){
	for(auto &i : e[x]){
		if(vis[i.x] || i.x == p) continue;
		if(s[i.x] > n / 2) return cd(i.x, x, n);
	}
	return x;
}

void dd(vector<int> &v, int x, int p, int d, int k){
	if(vis[x] || d > k) return;
	if(chk[x]) v.push_back(d);
	for(auto &i : e[x]) if(i.x != p) dd(v, i.x, x, d + i.c, k);
}

ll f(int x, int k){
	sd(x, 0);
	x = cd(x, 0, s[x]);
	for(int i = 0; i < e[x].size(); i++){
		dd(cv[i], e[x][i].x, x, e[x][i].c, k);
		for(auto &j : cv[i]) av.push_back(j);
		sort(cv[i].begin(), cv[i].end());
	}
	sort(av.begin(), av.end());
	ll ret = 0;
	for(int i = 0; i < e[x].size(); i++){
		for(auto &j : cv[i]){
			ret += (int)(upper_bound(av.begin(), av.end(), k - j) - av.begin()) -
				   (int)(upper_bound(cv[i].begin(), cv[i].end(), k - j) - cv[i].begin());
		}
		vector<int>().swap(cv[i]);
	}
	ret /= 2; ret += chk[x] * (int)av.size();
	vector<int>().swap(av);
	vis[x] = 1;
	for(auto &i : e[x]){
		if(ret >= K) return K;
		if(!vis[i.x]) ret += f(i.x, k);
	}
	return ret;
}

int can(int k){ fill(vis + 1, vis + n + 1, 0); return f(1, k) >= K; }

int main(){
	scanf("%d%d%lld", &n, &m, &K);
	for(int i = 2, x, y; i <= n; i++){
		scanf("%d%d", &x, &y);
		e[i].push_back({x, y});
		e[x].push_back({i, y});
	}
	for(int i = 0, x; i < m; i++){
		scanf("%d", &x);
		chk[x] = 1;
	}
	int s = 1, e = 3e7;
	for(int m; s <= e; ){
		m = (s + e) / 2;
		if(can(m)) e = m - 1;
		else s = m + 1;
	}
	printf("%d\n", s);
}

Compilation message

cabana.cpp: In function 'll f(int, int)':
cabana.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < e[x].size(); i++){
                   ^
cabana.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < e[x].size(); i++){
                   ^
cabana.cpp: In function 'int main()':
cabana.cpp:63: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:65:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^
cabana.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7884 KB Output is correct
2 Correct 36 ms 8116 KB Output is correct
3 Correct 39 ms 8400 KB Output is correct
4 Correct 246 ms 9336 KB Output is correct
5 Correct 786 ms 11844 KB Output is correct
6 Correct 3076 ms 14628 KB Output is correct
7 Correct 2213 ms 14980 KB Output is correct
8 Correct 4066 ms 16996 KB Output is correct
9 Correct 1549 ms 16028 KB Output is correct
10 Correct 4176 ms 17184 KB Output is correct
11 Correct 4643 ms 17180 KB Output is correct
12 Correct 4346 ms 17180 KB Output is correct
13 Correct 5306 ms 17184 KB Output is correct
14 Correct 5249 ms 17184 KB Output is correct
15 Correct 5353 ms 17184 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7884 KB Output is correct
2 Correct 9 ms 8148 KB Output is correct
3 Correct 53 ms 8676 KB Output is correct
4 Correct 513 ms 11580 KB Output is correct
5 Correct 169 ms 9732 KB Output is correct
6 Correct 256 ms 10656 KB Output is correct
7 Correct 276 ms 11352 KB Output is correct
8 Correct 413 ms 11988 KB Output is correct
9 Correct 579 ms 11580 KB Output is correct
10 Correct 403 ms 12024 KB Output is correct
11 Correct 23 ms 8148 KB Output is correct
12 Correct 536 ms 11580 KB Output is correct
13 Correct 633 ms 13360 KB Output is correct
14 Correct 423 ms 11712 KB Output is correct
15 Correct 593 ms 13100 KB Output is correct
16 Correct 829 ms 11448 KB Output is correct
17 Correct 563 ms 11448 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7884 KB Output is correct
2 Correct 56 ms 8016 KB Output is correct
3 Correct 76 ms 8148 KB Output is correct
4 Correct 276 ms 8676 KB Output is correct
5 Correct 989 ms 9908 KB Output is correct
6 Correct 1996 ms 11568 KB Output is correct
7 Correct 2859 ms 11452 KB Output is correct
8 Correct 2786 ms 13140 KB Output is correct
9 Correct 1733 ms 12080 KB Output is correct
10 Correct 5426 ms 13092 KB Output is correct
11 Correct 2996 ms 13264 KB Output is correct
12 Correct 4583 ms 13092 KB Output is correct
13 Correct 2516 ms 13104 KB Output is correct
14 Correct 3326 ms 13092 KB Output is correct
15 Correct 2766 ms 13040 KB Output is correct
16 Correct 3789 ms 17184 KB Output is correct
17 Correct 559 ms 15720 KB Output is correct
18 Correct 2996 ms 14852 KB Output is correct