#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 0x1fffffffffffffff;
#define overload3(a,b,c,d,...) d
#define all(a) begin(a), end(a)
#define rep1(n) for(int i = 0; i < n; i++)
#define rep2(i,n) for(int i = 0; i < n; i++)
#define rep3(i,a,b) for(int i = a; i < b; i++)
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i : a)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
struct SlidMax{
deque<pll> q;
ll low = 0, high = 0;
ll pop(){
ll ans = q[0].first;
if(q.front().second == low++) q.pop_front();
return ans;
}
void push(ll x){
while(q.size() && q.back().first <= x) q.pop_back();
q.emplace_back(x, high++);
}
};
ll Diameter(const vector<vector<pll>>& g){
ll n = g.size();
vector<ll> cost(n, INF);
vector<bool> used(n);
queue<ll> q;
q.push(0);
cost[0] = 0;
while(q.size()){
ll at = q.front();
q.pop();
if(used[at]) continue;
used[at] = 1;
each(i, g[at]) if(chmin(cost[i.first], cost[at] + i.second)) q.push(i.first);
}
ll d = max_element(all(cost)) - cost.begin();
cost.assign(n, INF);
used.assign(n, 0);
q.push(d);
cost[d] = 0;
while(q.size()){
ll at = q.front();
q.pop();
if(used[at]) continue;
used[at] = 1;
each(i, g[at]) if(chmin(cost[i.first], cost[at] + i.second)) q.push(i.first);
}
return *max_element(all(cost));
}
ll solve(const vector<vector<pll>>& g){
ll n = g.size();
ll at = 0;
vector<bool> circle(n);
rep(n) at = g[at][0].first;
rep(n){
at = g[at][0].first;
circle[at] = 1;
}
vector<ll> d(n);
auto dfs = [&](ll from, ll at, const auto& f) -> void {
rep(i, 1, g[at].size()){
ll to = g[at][i].first;
if(to != from && !circle[to]){
f(at, to, f);
chmax(d[at], d[to] + g[at][i].second);
}
}
};
rep(n) if(circle[i]) dfs(-1, i, dfs);
ll ans = Diameter(g);
ll circle_size = accumulate(all(circle), 0);
vector<ll> len(circle_size * 2 + 1);
rep(circle_size * 2){
ll to = g[at][0].first;
len[i + 1] = len[i] + g[at][0].second;
at = to;
}
SlidMax mx;
rep(circle_size - 1){
at = g[at][0].first;
mx.push(len[i + 1] + d[at]);
}
at = g[at][0].first;
rep(circle_size){
chmax(ans, mx.pop() - len[i] + d[at]);
mx.push(len[circle_size + i] + d[at]);
at = g[at][0].first;
}
return ans;
}
int main(){
ll n;
cin >> n;
vector<vector<pll>> G(n);
rep(n){
ll a, b;
cin >> a >> b;
a--;
G[i].emplace_back(a, b);
}
rep(n) G[G[i][0].first].emplace_back(i, G[i][0].second);
vector<ll> idx(n, -1);
ll ans = 0;
rep(n) if(idx[i] == -1){
vector<ll> vertex;
auto cc = [&](ll at, const auto& f) -> void {
idx[at] = vertex.size();
vertex.push_back(at);
each(i, G[at]) if(idx[i.first] == -1) f(i.first, f);
};
cc(i, cc);
ll n = vertex.size();
vector<vector<pll>> g(n);
rep(n){
auto& edge = G[vertex[i]][0];
g[i].emplace_back(idx[edge.first], edge.second);
}
rep(n){
auto& edge = G[vertex[i]][0];
g[idx[edge.first]].emplace_back(i, edge.second);
}
ans += solve(g);
}
cout << ans << endl;
}
Compilation message
islands.cpp: In instantiation of 'solve(const std::vector<std::vector<std::pair<long long int, long long int> > >&)::<lambda(ll, ll, const auto:1&)> [with auto:1 = solve(const std::vector<std::vector<std::pair<long long int, long long int> > >&)::<lambda(ll, ll, const auto:1&)>; ll = long long int]':
islands.cpp:78:40: required from here
islands.cpp:10:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep3(i,a,b) for(int i = a; i < b; i++)
^
islands.cpp:6:32: note: in expansion of macro 'rep3'
#define overload3(a,b,c,d,...) d
^
islands.cpp:11:18: note: in expansion of macro 'overload3'
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
^~~~~~~~~
islands.cpp:70:9: note: in expansion of macro 'rep'
rep(i, 1, g[at].size()){
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
256 KB |
Output is correct |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct |
| 6 |
Correct |
5 ms |
256 KB |
Output is correct |
| 7 |
Correct |
4 ms |
256 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
256 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
512 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1280 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
2296 KB |
Output is correct |
| 2 |
Correct |
55 ms |
8440 KB |
Output is correct |
| 3 |
Correct |
36 ms |
4600 KB |
Output is correct |
| 4 |
Correct |
19 ms |
2432 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
77 ms |
11760 KB |
Output is correct |
| 2 |
Correct |
128 ms |
13276 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
304 ms |
39656 KB |
Output is correct |
| 2 |
Correct |
285 ms |
36020 KB |
Output is correct |
| 3 |
Correct |
371 ms |
60872 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
557 ms |
39152 KB |
Output is correct |
| 2 |
Correct |
680 ms |
115040 KB |
Output is correct |
| 3 |
Correct |
697 ms |
96036 KB |
Output is correct |
| 4 |
Runtime error |
850 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1171 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1255 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
