제출 #1314656

#제출 시각아이디문제언어결과실행 시간메모리
1314656joshjuiceFirefighting (NOI20_firefighting)C++20
100 / 100
128 ms33612 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

#define pb push_back
#define eb emplace_back
#define fr first
#define sc second
#define sz(a) a.size()
#define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--))
#define mnto(x,y) x = min(x, (__typeof__(x))y)
#define mxto(x,y) x = max(x, (__typeof__(x))y)

int n;
ll k;
vi ans;
vector<pii> adj[300005];

pair<bool, ll> dfs(int idx, int p, ll d) {
	// mo is max distance from station child
	// mu is max distance from no-station child
	ll mo = LLONG_MIN, mu = 0;
	for (pii &pr : adj[idx]) {
		if (pr.fr != p) {
			pair<bool, ll> res = dfs(pr.fr, idx, pr.sc);
			if (res.fr) mxto(mo, res.sc);
			else mxto(mu, res.sc);
		}
	}
	pair<bool, ll> si;
	if (mo >= mu) si = {1, mo-d};
	else si = {0, mu+d};
	if (!si.fr && si.sc > k) {
		ans.pb(idx);
		si = {1, k-d};
	}
	if (si.fr && si.sc < 0) si = {0, 0};
	return si;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	rep(i, 1, n) {
		int a, b, w;
		cin >> a >> b >> w;
		a--; b--;
		adj[a].eb(b, w);
		adj[b].eb(a, w);
	}
	dfs(0, -1, LLONG_MAX/4);
	cout << sz(ans) << '\n';
	rep(i, 0, sz(ans)) cout << ans[i]+1 << ' ';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...