| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 219651 | tatyam | Islands (IOI08_islands) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
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; }
template<class F> class [[nodiscard]] FixPoint : private F {
public:
explicit constexpr FixPoint(F&& f) noexcept : F(std::forward<F>(f)){}
template<typename... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept(noexcept(F::operator()(std::declval<FixPoint>(), std::declval<Args>()...))){
return F::operator()(*this, std::forward<Args>(args)...);
}
};
struct SlidMax{
deque<pair<ll, int>> q; // 8MB?
int 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<pii>>& g){
int n = g.size();
vector<ll> cost(n, INF); // 8MB
vector<bool> used(n); // 1MB
queue<int> q; // 6MB
q.push(0);
cost[0] = 0;
while(q.size()){
int at = q.front();
q.pop();
if(used[at]) continue;
used[at] = 1;
each(i, g[at]) if(cost[i.first] == INF){
cost[i.first] = cost[at] + i.second;
q.push(i.first);
}
}
int d = max_element(all(cost)) - cost.begin();
cost.assign(n, INF);
used.assign(n, 0);
q.push(d);
cost[d] = 0;
while(q.size()){
int at = q.front();
q.pop();
if(used[at]) continue;
used[at] = 1;
each(i, g[at]) if(cost[i.first] == INF){
cost[i.first] = cost[at] + i.second;
q.push(i.first);
}
}
return *max_element(all(cost));
}
ll solve(const vector<vector<pii>>& g){
int n = g.size();
int at = 0;
vector<bool> circle(n); // 1MB
rep(n) at = g[at][0].first;
rep(n){
at = g[at][0].first;
circle[at] = 1;
}
vector<ll> d(n); // 8MB
rep(n) if(circle[i]) FixPoint{[&circle, &g, &d](const auto& f, int from, int at) -> void { // 20MB
rep(i, 1, g[at].size()){
const int to = g[at][i].first;
if(to != from && !circle[to]){
f(at, to);
chmax(d[at], d[to] + g[at][i].second);
}
}
}}(-1, i);
ll ans = Diameter(g);
int circle_size = accumulate(all(circle), 0);
vector<ll> len(circle_size * 2 + 1); // 16MB
rep(circle_size * 2){
int 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(){
int n;
cin >> n;
vector<vector<pii>> G(n); // 24MB
rep(n){
int 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<int> idx(n, -1); // 4MB
ll ans = 0;
rep(n) if(idx[i] == -1){
vector<int> vertex = {i};
idx[i] = 0;
for(int i = 0; i < vertex.size(); i++){
for(auto& [to, d] : G[vertex[i]]){
if(idx[to] == -1){
idx[to] = vertex.size();
vertex.push_back(to);
}
}
}
int n = vertex.size();
vector<vector<pii>> g(n);
rep(n){
auto& edge = G[vertex[i]][0];
g[i].emplace_back(idx[edge.first], edge.second);
}
each(i, vertex){
G[i].clear();
G[i].shrink_to_fit();
}
vertex.clear();
vertex.shrink_to_fit();
rep(n){
auto& edge = g[i][0];
g[edge.first].emplace_back(i, edge.second);
}
ans += solve(g);
}
cout << ans << endl;
}