oj.uz

Submission #20879

# Submission time Handle Problem Language Result Execution time Memory
20879 2017-03-03T05:45:37 Z kdh9949 오두막집 (GA7_cabana) C++14
63 / 100
 6000 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]);
	vector<int>().swap(av);
	for(int i = 0; i < e[x].size(); i++){
		vector<int>().swap(cv[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 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:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < e[x].size(); i++){
                   ^
cabana.cpp:45: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:60: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:62: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:67: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 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 3 ms 7884 KB Output is correct
5 Correct 0 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 3 ms 7884 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7884 KB Output is correct
2 Correct 53 ms 8116 KB Output is correct
3 Correct 59 ms 8396 KB Output is correct
4 Correct 289 ms 9332 KB Output is correct
5 Correct 906 ms 11840 KB Output is correct
6 Correct 3146 ms 14628 KB Output is correct
7 Correct 2226 ms 14976 KB Output is correct
8 Correct 4386 ms 16996 KB Output is correct
9 Correct 2009 ms 16028 KB Output is correct
10 Correct 4103 ms 17184 KB Output is correct
11 Correct 4909 ms 17180 KB Output is correct
12 Correct 4903 ms 17184 KB Output is correct
13 Correct 5433 ms 17180 KB Output is correct
14 Correct 5369 ms 17180 KB Output is correct
15 Correct 5336 ms 17184 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 3 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 6 ms 7884 KB Output is correct
2 Correct 49 ms 8148 KB Output is correct
3 Correct 199 ms 8676 KB Output is correct
4 Correct 1496 ms 11580 KB Output is correct
5 Correct 603 ms 9732 KB Output is correct
6 Correct 1008 ms 10656 KB Output is correct
7 Correct 1246 ms 11352 KB Output is correct
8 Correct 2319 ms 12000 KB Output is correct
9 Correct 1393 ms 11580 KB Output is correct
10 Correct 2083 ms 12024 KB Output is correct
11 Correct 59 ms 8148 KB Output is correct
12 Correct 1599 ms 11580 KB Output is correct
13 Correct 4016 ms 13376 KB Output is correct
14 Correct 1643 ms 11712 KB Output is correct
15 Correct 3546 ms 13104 KB Output is correct
16 Correct 1749 ms 11448 KB Output is correct
17 Correct 1563 ms 11448 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7884 KB Output is correct
2 Correct 73 ms 8016 KB Output is correct
3 Correct 73 ms 8148 KB Output is correct
4 Correct 309 ms 8676 KB Output is correct
5 Correct 1166 ms 9912 KB Output is correct
6 Correct 3093 ms 11568 KB Output is correct
7 Correct 2863 ms 11456 KB Output is correct
8 Correct 4646 ms 13212 KB Output is correct
9 Correct 2913 ms 12080 KB Output is correct
10 Correct 5059 ms 13096 KB Output is correct
11 Correct 5059 ms 13240 KB Output is correct
12 Execution timed out 6000 ms 13124 KB Execution timed out
13 Halted 0 ms 0 KB -