/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 1000000;
int N;
struct Edge {
int to;
int len;
};
vector <Edge> adj[N_MAX + 2];
bool seen[N_MAX + 2];
Edge par[N_MAX + 2];
tuple <int, int, int> backEdge;
void dfs (int u) {
seen[u] = true;
for (Edge e : adj[u]) {
if (seen[e.to] == false) {
par[e.to] = Edge{u, e.len};
dfs(e.to);
} else if (e.to != par[u].to) {
backEdge = make_tuple(u, e.to, e.len);
}
}
}
bool root[N_MAX + 2];
ll maxAny[N_MAX + 2];
ll maxDown[N_MAX + 2];
void compute (int u) {
vector <ll> maxDowns;
for (Edge e : adj[u]) {
if (seen[e.to] == false && root[e.to] == false) {
compute(e.to);
maxAny[u] = max(maxAny[u], maxAny[e.to]);
maxDown[u] = max(maxDown[u], maxDown[e.to] + e.len);
maxDowns.push_back(maxDown[e.to] + e.len);
}
}
sort(maxDowns.begin(), maxDowns.end(), greater <ll> ());
if ((int) maxDowns.size() >= 2) {
maxAny[u] = max(maxAny[u], maxDowns[0] + maxDown[1]);
}
maxAny[u] = max(maxAny[u], maxDown[u]);
}
vector <vector <int>> rootGroups;
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int u = 1; u <= N; u++) {
Edge e;
cin >> e.to >> e.len;
adj[u].push_back(Edge{e.to, e.len});
adj[e.to].push_back(Edge{u, e.len});
}
for (int u = 1; u <= N; u++) {
if (seen[u] == false) {
dfs(u);
int v1, v2, len; tie(v1, v2, len) = backEdge;
if (v1 == u) {
swap(v1, v2);
}
par[v2] = Edge{v1, len};
rootGroups.push_back({});
int v = v1;
while (v != v2) {
root[v] = true;
rootGroups.back().push_back(v);
v = par[v].to;
}
root[v] = true;
rootGroups.back().push_back(v);
}
}
fill(seen + 1, seen + N + 1, false);
for (int u = 1; u <= N; u++) {
if (root[u] == true) {
compute(u);
}
}
ll answer = 0;
for (vector <int> &roots : rootGroups) {
ll totalLen = 0;
ll maxLen = 0;
for (int u : roots) {
totalLen += par[u].len;
maxLen = max(maxLen, maxAny[u]);
}
multiset <ll> s; ll len = 0;
for (int i = (int) roots.size() - 1; i > 0; i--) {
len += par[roots[i]].len;
s.insert(maxDown[roots[i]] + len);
}
ll lazy = 0;
for (int i = 0, u = roots[0]; i < (int) roots.size(); i++) {
maxLen = max(maxLen, *s.rbegin() + lazy + maxDown[u]);
s.insert(maxDown[u] - lazy);
lazy += par[u].len;
u = par[u].to;
s.erase(s.find((maxDown[u] + totalLen) - lazy));
}
answer += maxLen;
}
cout << answer << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Runtime error |
162 ms |
131072 KB |
Execution killed with signal 9 |
3 |
Correct |
13 ms |
23892 KB |
Output is correct |
4 |
Runtime error |
159 ms |
131072 KB |
Execution killed with signal 9 |
5 |
Correct |
11 ms |
23764 KB |
Output is correct |
6 |
Runtime error |
161 ms |
131072 KB |
Execution killed with signal 9 |
7 |
Runtime error |
156 ms |
131072 KB |
Execution killed with signal 9 |
8 |
Runtime error |
152 ms |
131072 KB |
Execution killed with signal 9 |
9 |
Runtime error |
155 ms |
131072 KB |
Execution killed with signal 9 |
10 |
Runtime error |
158 ms |
131072 KB |
Execution killed with signal 9 |
11 |
Correct |
13 ms |
23764 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
164 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
165 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
161 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
182 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
213 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
163 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
374 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
356 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |