제출 #1320472

#제출 시각아이디문제언어결과실행 시간메모리
1320472samarthkulkarniFirefighting (NOI20_firefighting)C++20
3 / 100
309 ms30828 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define vi vector<long long> #define all(x) x.begin(), x.end() #define endl "\n" #define pr pair<ll, ll> #define ff first #define ss second void solution(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); solution(); return 0; } const int N = 3e5+10; vector<pr> adj[N]; ll sz[N]; bool vis[N]; bool safe[N]; ll n, k; vi res; ll get_sz(int a, int p) { sz[a] = 0; for (auto [b, w] : adj[a]) { if (vis[b] || safe[b] || b == p) continue; sz[a] += w + get_sz(b, a); } return sz[a]; } int centroid(int a, int p, ll l) { for (auto [b, w] : adj[a]) { if (!vis[b] && !safe[b] && b != p && sz[b]*2 > l) return centroid(b, a, l); } return a; } void add_safe(int a, int p, ll d) { if (d > k) return; safe[a] = true; for (auto [b, w] : adj[a]) { if (vis[b] || safe[b] || b == p) continue; add_safe(b, a, d+w); } } void solve(int a, int p) { int c = centroid(a, p, get_sz(a, p)); vis[c] = true; if (!safe[c]) { res.push_back(c); safe[c] = true; for (auto [b, w] : adj[c]) { if (vis[b] || safe[b]) continue; add_safe(b, c, w); } } for (auto [b, w] : adj[c]) { if (vis[b]) continue; solve(b, c); } } void solution() { cin >> n >> k; for (int i = 1; i < n; i++) { ll a, b, w; cin >> a >> b >> w; adj[a].push_back({b, w}); adj[b].push_back({a, w}); } solve(1, 1); cout << res.size() << endl; for (auto val : res) cout << val << " "; }
#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...