# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
523937 | 2022-02-08T12:37:52 Z | qwerasdfzxcl | Firefighting (NOI20_firefighting) | C++14 | 557 ms | 37808 KB |
#include <bits/stdc++.h> typedef long long ll; using namespace std; vector<pair<int, ll>> adj[300300]; pair<int, ll> par[300300]; ll dep[300300]; int deg[300300], visited[300300]; priority_queue<pair<ll, int>> pq; void dfs(int s, int pa = -1){ deg[s] = adj[s].size(); for (auto &v:adj[s]) if (v.first!=pa){ par[v.first] = {s, v.second}; dep[v.first] = dep[s] + v.second; dfs(v.first, s); } } void dfs2(int s, ll K){ visited[s] = 1; for (auto &v:adj[s]) if (!visited[v.first]){ if (v.second<=K) dfs2(v.first, K-v.second); else{ deg[v.first]--; if (deg[v.first]==1) pq.emplace(dep[v.first], v.first); } } } int main(){ int n; ll D; scanf("%d %lld", &n, &D); for (int i=0;i<n-1;i++){ int x, y; ll z; scanf("%d %d %lld", &x, &y, &z); adj[x].emplace_back(y, z); adj[y].emplace_back(x, z); } dfs(1); for (int i=1;i<=n;i++) if (deg[i]==1) pq.emplace(dep[i], i); vector<int> ans; while(!pq.empty()){ auto cur = pq.top(); pq.pop(); if (visited[cur.second]) continue; int s = cur.second; ll rem = D; while(par[s].first && par[s].second<=rem){ rem -= par[s].second; s = par[s].first; } ans.push_back(s); dfs2(s, D); } printf("%d\n", (int)ans.size()); for (auto &x:ans) printf("%d ", x); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 557 ms | 37776 KB | Output is correct |
2 | Correct | 510 ms | 37808 KB | Output is correct |
3 | Correct | 161 ms | 19064 KB | Output is correct |
4 | Correct | 449 ms | 36976 KB | Output is correct |
5 | Correct | 5 ms | 7372 KB | Output is correct |
6 | Incorrect | 4 ms | 7356 KB | Integer parameter [name=F] equals to 0, violates the range [1, 1] |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7372 KB | Output is correct |
2 | Correct | 7 ms | 7372 KB | Output is correct |
3 | Incorrect | 5 ms | 7244 KB | Integer parameter [name=F] equals to 0, violates the range [1, 1] |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7328 KB | Output is correct |
2 | Correct | 8 ms | 7372 KB | Output is correct |
3 | Correct | 4 ms | 7372 KB | Output is correct |
4 | Correct | 6 ms | 7348 KB | Output is correct |
5 | Correct | 4 ms | 7372 KB | Output is correct |
6 | Correct | 6 ms | 7372 KB | Output is correct |
7 | Correct | 5 ms | 7372 KB | Output is correct |
8 | Incorrect | 4 ms | 7356 KB | Integer parameter [name=F] equals to 0, violates the range [1, 1] |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 490 ms | 37700 KB | Output is correct |
2 | Correct | 279 ms | 23848 KB | Output is correct |
3 | Correct | 345 ms | 26980 KB | Output is correct |
4 | Correct | 241 ms | 24408 KB | Output is correct |
5 | Correct | 5 ms | 7372 KB | Output is correct |
6 | Incorrect | 6 ms | 7344 KB | Integer parameter [name=F] equals to 0, violates the range [1, 1] |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 7616 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 422 ms | 34136 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |