Submission #682621

#TimeUsernameProblemLanguageResultExecution timeMemory
682621BhavayGoyalFirefighting (NOI20_firefighting)C++14
100 / 100
331 ms41292 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define ld long double #define ar array #define vi vector<int> #define vii vector<vector<int>> #define pii pair<int, int> #define pb push_back #define all(x) x.begin(), x.end() #define f first #define s second #define endl "\n" const int MOD = 1e9+7; const int inf = 1e9; const int linf = 1e18; const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1}; const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1}; // -------------------------------------------------- Main Code -------------------------------------------------- const int N = 3e5+5; int n, k, isUsed[N]; vi ans; vector<pii> g[N]; int dfs(int src, int par, int lastWt) { int req = 0, ext = linf; for (auto child : g[src]) { int ch = child.f, wt = child.s; if (ch == par) continue; int x = dfs(ch, src, wt); if (!isUsed[ch]) req = max(req, x); else ext = min(ext, x); } if (ext+req <= k) { isUsed[src] = true; return lastWt+ext; } if (lastWt+req <= k) { return lastWt+req; } ans.pb(src); isUsed[src] = true; return lastWt; // have to add fire station on this node } void sol() { cin >> n >> k; for (int i = 0; i < n-1; i++) { int a, b, c; cin >> a >> b >> c; --a; --b; g[a].pb({b, c}); g[b].pb({a, c}); } dfs(0, -1, linf); cout << ans.size() << endl; reverse(all(ans)); for (auto i : ans) cout << i+1 << " "; cout << endl; } signed main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { sol(); } return 0; }

Compilation message (stderr)

Firefighting.cpp: In function 'void sol()':
Firefighting.cpp:76:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   76 |     for (auto i : ans) cout << i+1 << " "; cout << endl;
      |     ^~~
Firefighting.cpp:76:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   76 |     for (auto i : ans) cout << i+1 << " "; cout << endl;
      |                                            ^~~~
#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...