Submission #1312988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312988		julia_08	Islands (IOI08_islands)	C++20	80 / 100	497 ms	142716 KiB

islands

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int MAXN = 2e6 + 10;
const int INF = 1e18;
 
int pai[MAXN], marc[MAXN], deg[MAXN];
 
int dp[MAXN], dp2[MAXN];
 
pair<int, int> best[MAXN];
 
vector<pair<int, int>> adj[MAXN];
 
int n;
 
int tot = 0;
 
void lenhadora(){
 
  queue<int> q;
 
  for(int i=1; i<=n; i++) pai[i] = i;
 
  for(int i=1; i<=n; i++){
    if(deg[i] == 1){
      q.push(i);
      marc[i] = 1;
    }
  }
 
  while(!q.empty()){
 
    int v = q.front();
    q.pop();
    
    dp2[v] = max(dp2[v], best[v].first + best[v].second);
 
    for(auto [u, w] : adj[v]){
 
      deg[u] --;
      if(marc[u]) continue;
 
      pai[v] = u;
 
      dp[u] = max(dp[u], dp[v] + w);
      dp2[u] = max(dp2[u], dp2[v]);
 
      if(dp[v] + w >= best[u].first){
        best[u] = {dp[v] + w, best[u].first};
      } else best[u].second = max(best[u].second, dp[v] + w);
 
      if(deg[u] < 2){
        q.push(u);
        marc[u] = 1;
      }
 
    }
 
  }  
  
  for(int i=1; i<=n; i++) dp2[i] = max(dp2[i], best[i].first + best[i].second);
 
  for(int i=1; i<=n; i++) marc[i] = 0;
 
}
 
void process(int v){
 
  int cur = 0;
 
  int max_a = -INF, max_b = -INF;
 
  vector<pair<int, int>> cycle;
 
  int sz = 0;
  
  marc[0] = 1;
 
  while(!marc[v]){
 
    marc[v] = 1;
 
    pair<int, int> nxt = {0, 0};
 
    for(auto [u, w] : adj[v]){
      if(!marc[u] && pai[u] == u){
        if(nxt.first){
          sz += w;
        } else nxt = {u, w};
      }
    }
 
    cycle.push_back({v, nxt.second});
 
    sz += nxt.second;
    v = nxt.first;
 
  }
  
  int d = 0;
 
  for(auto [v, w] : cycle){
   
    cur = max(cur, max_a + dp[v] + d);
    cur = max(cur, max_b + dp[v] + sz - d);
 
    cur = max(cur, dp2[v]);
 
    max_a = max(max_a, dp[v] - d);
    max_b = max(max_b, dp[v] + d);
 
    d += w;
 
  }
 
  tot += cur;
 
}
 
int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n;
  
  for(int i=1; i<=n; i++){
 
    int a, b; cin >> a >> b;
 
    adj[i].push_back({a, b});
    adj[a].push_back({i, b});
 
    deg[i] ++; deg[a] ++;
 
  }
 
  lenhadora();
 
  for(int i=1; i<=n; i++){
 
    if(marc[i] || pai[i] != i) continue;
    process(i);
 
  }
 
  cout << tot << "\n";
 
  return 0;
}  

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10