oj.uz

답안 #1018639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018639 2024-07-10T07:45:32 Z Muaath_5 Islands (IOI08_islands) C++17
70 / 100
 478 ms 131072 KB 
    #pragma GCC optimize("Og")
    #include <bits/stdc++.h>
    #define ll long long
    #define pii pair<int, int>
    using namespace std;
     
    const int N = 1e6+5;
     
    // input
    int n;
    vector<pair<int, int>> adj[N]; // 8M
    map<pii, int> edge; // count duplicate // 12M
    map<pii, int> we; // weight of edge // 12M
     
    // dfs
    vector<bool> vis(N); // 1M or less
    vector<int> stck; // 1M
    vector<int> cyc; // 1M
     
    // diameter dfs
    pii remedge;
    int blk[2];
    int mx[N]; // 1M
     
    ll a[N]; // 8M
     
    //ll pref[N]; // 8M
    //ll mxdep[N]; // 8M
     
    void dfs(int node, int par=0) {
      vis[node] = 1;
      stck.push_back(node);
      for (auto &[ch, cost] : adj[node]) {
        if (!vis[ch])
          dfs(ch, node);
        else if (!cyc.size() && edge[{node, ch}] == 2) {
          cyc.push_back(node);
          cyc.push_back(ch);
        }
        else if (!cyc.size() && vis[ch] && ch != par) {
          bool st = 0;
          for (int cur : stck) {
            if (cur == ch) st = 1;
            if (st) cyc.push_back(cur);
          }
        }
     
      }
      stck.pop_back();
    }
     
     
    ll farthest_dp(int node, int par=0) {
      mx[node] = node;
      ll mxdep = 0;
      for (auto [ch, cost] : adj[node]) {
        if (blk[0] == ch || blk[1] == ch || ch == par) continue;
        if (make_pair(node, ch) != remedge && make_pair(ch, node) != remedge) {
          ll mxdepch = farthest_dp(ch, node);
          if (mxdepch + cost > mxdep) {
            mxdep = mxdepch + cost;
            mx[node] = mx[ch];
          }
        }
      }
      return mxdep;
    }
     
    ll solve_for(int node)
    {
      cyc.clear();
      dfs(node);
      const ll L = cyc.size();
      //assert(L > 1);
      // cerr << "#" << node << ": ";	
      // cerr << L << ": ";
      // for(int i:cyc)cerr<<i<<' ';
      // cerr<<"| ";
     
     
     
      // remove an edge from the cycle and find diameter
      if (L > 2)
        remedge = {cyc[0], cyc[1]};
      else
        remedge = {-1, -1};
      farthest_dp(node);
      int fr = mx[node];
      ll diam = farthest_dp(fr);
     
     
     
      // a[i] = max depth of tree going from i not in cycle direction 
      // prefix sums
      for (int i = 0; i < L; i++) {
        blk[0] = cyc[(i+1)%L];
        blk[1] = cyc[(i-1+L)%L];
        a[i] = farthest_dp(cyc[i]);
      }
     
     
      // for (int i = 0; i < L; i++)
      // cerr << a[i] << ' ';
      // cerr << "| ";
     
      // cost of path(i,j) = a[i] + a[j] + (p[i] - p[j]);
      // maintain maximum a[j] - p[j], and the answer for suffix i:
      // 	
      ll prvmx = 0, prvmx2 = 0;;
      ll sol = 0;
      ll pref = 0;
      for (int i = 1; i < L; i++)
        pref += we[{cyc[i], cyc[i-1]}];
     
      const ll LL = pref + we[{cyc[L-1], cyc[0]}];
      if (L == 2) {
        sol = *max_element(a, a+L) + we[{cyc[0], cyc[1]}];
        goto RET;
      }
     
      pref = 0;
      prvmx = prvmx2 = a[0];
      for (int i = 1; i < L; i++) {
        pref += we[{cyc[i], cyc[i-1]}];
        sol = max(sol, a[i] + pref + prvmx);
        sol = max(sol, LL + a[i] - pref + prvmx2);
        prvmx2 = max(prvmx2, a[i] + pref);
        prvmx = max(prvmx, a[i] - pref);
      }
     
      RET:
      return max(diam, sol);
    }
     
     
    signed main()
    {
      ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
      // stck.reserve(N/2);
      // cyc.reserve(N/2);
      cin >> n;
      for (int i = 1; i <= n; i++) {
        int u, w;
        cin >> u >> w;
        adj[i].push_back({u, w});
        adj[u].push_back({i, w});
        edge[{i,u}]++, edge[{u,i}]++;
        we[{i, u}] = we[{u, i}] = max(we[{i, u}], w);
      }
      ll sum = 0;
      for (int i = 1; i <= n; i++)
        if (!vis[i])
          sum += solve_for(i);
      cout << sum;
    }

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 27228 KB Output is correct
2 Correct 7 ms 27428 KB Output is correct
3 Correct 10 ms 27608 KB Output is correct
4 Correct 7 ms 27320 KB Output is correct
5 Correct 7 ms 27228 KB Output is correct
6 Correct 7 ms 27228 KB Output is correct
7 Correct 7 ms 27448 KB Output is correct
8 Correct 8 ms 27228 KB Output is correct
9 Correct 7 ms 27228 KB Output is correct
10 Correct 7 ms 27228 KB Output is correct
11 Correct 7 ms 27228 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 27736 KB Output is correct
2 Correct 9 ms 27688 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 27992 KB Output is correct
2 Correct 14 ms 28764 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 32092 KB Output is correct
2 Correct 64 ms 39964 KB Output is correct
3 Correct 34 ms 33744 KB Output is correct
4 Correct 19 ms 30300 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 45396 KB Output is correct
2 Correct 103 ms 59756 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 92244 KB Output is correct
2 Correct 320 ms 108824 KB Output is correct
3 Correct 389 ms 127404 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 273 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 478 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 395 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -