oj.uz

Submission #20878

# Submission time Handle Problem Language Result Execution time Memory
20878 2017-03-03T05:39:03 Z kdh9949 오두막집 (GA7_cabana) C++14
63 / 100
 6000 ms 15360 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];
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]);
	vector<int> av, cv[(int)e[x].size()];
	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());
		}
	}
	ret /= 2; ret += chk[x] * (int)av.size();
	vis[x] = 1;
	for(auto &i : e[x]) 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 i = 1; i <= 10; i++){
		fill(vis + 1, vis + n + 1, 0);
	}
	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:58: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:60: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:65: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 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 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 3 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 3 ms 5540 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5540 KB Output is correct
2 Correct 56 ms 5776 KB Output is correct
3 Correct 59 ms 6052 KB Output is correct
4 Correct 293 ms 6992 KB Output is correct
5 Correct 949 ms 9568 KB Output is correct
6 Correct 3186 ms 12800 KB Output is correct
7 Correct 2319 ms 12936 KB Output is correct
8 Correct 4606 ms 15168 KB Output is correct
9 Correct 2089 ms 13984 KB Output is correct
10 Correct 4189 ms 15220 KB Output is correct
11 Correct 4949 ms 15360 KB Output is correct
12 Correct 4889 ms 15352 KB Output is correct
13 Correct 5309 ms 15296 KB Output is correct
14 Correct 5383 ms 15296 KB Output is correct
15 Correct 5279 ms 15296 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 0 ms 5540 KB Output is correct
4 Correct 0 ms 5540 KB Output is correct
5 Correct 0 ms 5540 KB Output is correct
6 Correct 0 ms 5540 KB Output is correct
7 Correct 0 ms 5540 KB Output is correct
8 Correct 0 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 #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5540 KB Output is correct
2 Correct 46 ms 5804 KB Output is correct
3 Correct 203 ms 6332 KB Output is correct
4 Correct 1439 ms 9236 KB Output is correct
5 Correct 546 ms 7388 KB Output is correct
6 Correct 1043 ms 8312 KB Output is correct
7 Correct 1359 ms 9008 KB Output is correct
8 Correct 2226 ms 9824 KB Output is correct
9 Correct 1453 ms 9236 KB Output is correct
10 Correct 2166 ms 9708 KB Output is correct
11 Correct 63 ms 5804 KB Output is correct
12 Correct 1686 ms 9368 KB Output is correct
13 Correct 4239 ms 11464 KB Output is correct
14 Correct 1793 ms 9368 KB Output is correct
15 Correct 3776 ms 10800 KB Output is correct
16 Correct 2099 ms 9104 KB Output is correct
17 Correct 1689 ms 9104 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5540 KB Output is correct
2 Correct 79 ms 5804 KB Output is correct
3 Correct 83 ms 5804 KB Output is correct
4 Correct 313 ms 6332 KB Output is correct
5 Correct 1216 ms 7564 KB Output is correct
6 Correct 3473 ms 9416 KB Output is correct
7 Correct 2873 ms 9348 KB Output is correct
8 Correct 5009 ms 11052 KB Output is correct
9 Correct 3156 ms 9872 KB Output is correct
10 Correct 5493 ms 11132 KB Output is correct
11 Correct 5206 ms 11144 KB Output is correct
12 Execution timed out 6000 ms 11292 KB Execution timed out
13 Halted 0 ms 0 KB -