Compile Error
foo.cc:4:1: error: 'vector' does not name a type
4 | vector<pair<int, int>> adj[MAXN];
| ^~~~~~
foo.cc:5:1: error: 'vector' does not name a type
5 | vector<long long> weights(MAXN), depth(MAXN), totalWeight(MAXN);
| ^~~~~~
foo.cc: In function 'void dfs(int, int)':
foo.cc:7:5: error: 'totalWeight' was not declared in this scope
7 | totalWeight[node] = weights[node];
| ^~~~~~~~~~~
foo.cc:7:25: error: 'weights' was not declared in this scope
7 | totalWeight[node] = weights[node];
| ^~~~~~~
foo.cc:8:30: error: 'adj' was not declared in this scope
8 | for (auto [next, cost] : adj[node]) {
| ^~~
foo.cc:10:9: error: 'depth' was not declared in this scope
10 | depth[next] = depth[node] + cost;
| ^~~~~
foo.cc: In function 'int main()':
foo.cc:23:20: error: 'weights' was not declared in this scope
23 | cin >> weights[i];
| ^~~~~~~
foo.cc:24:13: error: 'adj' was not declared in this scope
24 | adj[i].clear();
| ^~~
foo.cc:29:13: error: 'adj' was not declared in this scope
29 | adj[u].push_back({v, c});
| ^~~
foo.cc:32:9: error: 'depth' was not declared in this scope
32 | depth.assign(N + 1, 0);
| ^~~~~
foo.cc:34:36: error: 'LLONG_MIN' was not declared in this scope
34 | long long maxCycleWeight = LLONG_MIN;
| ^~~~~~~~~
foo.cc:2:1: note: 'LLONG_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
1 | #include <iostream>
+++ |+#include <climits>
2 | using namespace std;
foo.cc:39:35: error: 'totalWeight' was not declared in this scope
39 | long long cycle = totalWeight[u] + totalWeight[v] - cost;
| ^~~~~~~~~~~
Code
#include <iostream>
using namespace std;
const int MAXN = 200005;
vector<pair<int, int>> adj[MAXN];
vector<long long> weights(MAXN), depth(MAXN), totalWeight(MAXN);
void dfs(int node, int parent) {
totalWeight[node] = weights[node];
for (auto [next, cost] : adj[node]) {
if (next == parent) continue;
depth[next] = depth[node] + cost;
dfs(next, node);
totalWeight[node] += totalWeight[next];
}
}
int main() {
int T;
cin >> T;
while (T--) {
int N;
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> weights[i];
adj[i].clear();
}
for (int i = 0; i < N - 1; ++i) {
int u, v, c;
cin >> u >> v >> c;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
depth.assign(N + 1, 0);
dfs(1, 0);
long long maxCycleWeight = LLONG_MIN;
for (int u = 1; u <= N; ++u) {
for (int v = u + 1; v <= N; ++v) {
// Use depth to calculate cost of path from u to v
long long cost = depth[u] + depth[v];
long long cycle = totalWeight[u] + totalWeight[v] - cost;
maxCycleWeight = max(maxCycleWeight, cycle);
}
}
cout << maxCycleWeight << '\n';
}
return 0;
}Information
- Submit By
-
Mahir Mohammad Khawja(0182420012101005) LV 0
- Type
- Submission
- Problem
- P1205 E. Make Cycle in Tree
- Contest
- Educational Round 1
- Language
- C++17 (G++ 13.2.0)
- Submit At
- 2025-07-14 16:15:34
- Judged At
- 2025-07-14 16:15:34
- Judged By
-
judge
- Score
- 0
- Total Time
- 0ms
- Peak Memory
- 0 Bytes