oj.uz

답안 #20880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20880 2017-03-03T06:00:51 Z kdh9949 오두막집 (GA7_cabana) C++14
0 / 100
 16 ms 7884 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]);
	}
	vector<int>().swap(av);
	ret /= 2; ret += chk[x] * (int)av.size();
	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
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 7884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 7884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 7884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 7884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 7884 KB Output isn't correct
2 Halted 0 ms 0 KB -