Submission #1312899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312899		julia_08	Islands (IOI08_islands)	C++20	43 / 100	237 ms	125876 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]);

      if(deg[u] < 2){
        q.push(u);
        marc[u] = 1;
      }

    }

  }  

  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;

  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: 3 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 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