Submission #20879

#	Time	Username	Problem	Language	Result	Execution time	Memory
20879		kdh9949	오두막집 (GA7_cabana)	C++14	63 / 100	6000 ms	17184 KiB

cabana

#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 (stderr)

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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 0 / 37