oj.uz

답안 #501732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
501732 2022-01-04T12:13:53 Z 600Mihnea Islands (IOI08_islands) C++17
51 / 100
 1111 ms 119464 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge {
  int a, b, cost;
  bool seen = false;
};

const int N = (int) 1e6 + 7;
const ll INF = (ll) 1e18;
int n;
int parrent[N];
Edge graph_edges[N];
vector<int> g[N], verts;
bool vis[N];
int dep[N];
int epar[N];

vector<int> geallonp(int a, int b) {
  vector<int> p1, p2;
  while (a != b) {
    if (dep[a] > dep[b]) {
      p1.push_back(a);
      a = parrent[a];
    } else {
      p2.push_back(b);
      b = parrent[b];
    }
  }
  p1.push_back(a);
  reverse(p2.begin(), p2.end());
  for (auto &x : p2) {
    p1.push_back(x);
  }
  return p1;
}

vector<int> geallonpedges(int a, int b) {
  vector<int> p1, p2;
  while (a != b) {
    if (dep[a] > dep[b]) {
      p1.push_back(epar[a]);
      a = parrent[a];
    } else {
      p2.push_back(epar[b]);
      b = parrent[b];
    }
  }
  reverse(p2.begin(), p2.end());
  for (auto &x : p2) {
    p1.push_back(x);
  }
  return p1;
}

bool blocked[N];
ll under[N];
ll bbpath[N];

void dfs(int a) {
  for (auto &i : g[a]) {
    int b = graph_edges[i].a + graph_edges[i].b - a;
    if (blocked[b] || b == parrent[a]) {
      continue;
    }
    dfs(b);
    bbpath[a] = max(bbpath[a], bbpath[b]);
    bbpath[a] = max(bbpath[a], under[b] + graph_edges[i].cost + under[a]);
    under[a] = max(under[a], under[b] + graph_edges[i].cost);
  }

}

ll sum[N];
bool v2[N];

ll solveComponent(int rootVertex) {
  ll sol = 0;
  verts.clear();

  queue<int> q;
  q.push(rootVertex);
  vis[rootVertex] = true;

  while (!q.empty()) {
    int a = q.front();
    q.pop();
    verts.push_back(a);
    for (auto &i : g[a]) {
      int b = graph_edges[i].a + graph_edges[i].b - a;
      if (!vis[b]) {
        dep[b] = 1 + dep[a];
        epar[b] = i;
        vis[b] = true;
        q.push(b);
        parrent[b] = a;
        graph_edges[i].seen = true;
      }
    }
  }
  vector<int> nnseeng;
  for (auto &v : verts) {
    for (auto &i : g[v]) {
      if (!graph_edges[i].seen) {
        graph_edges[i].seen = true;
        nnseeng.push_back(i);
      }
    }
  }
  {
    int index = nnseeng[0];
    int a = graph_edges[index].a;
    int b = graph_edges[index].b;
    int cost = graph_edges[index].cost;
    vector<int> path = geallonp(a, b);
    vector<int> edges = geallonpedges(a, b);
    vector<ll> value;
    edges.push_back(index);

    vector<int> ord;

    for (auto &v : path) {
      blocked[v] = true;
      q.push(v);
      v2[v] = true;
    }


    while (!q.empty()) {
      int a = q.front();
      q.pop();
      ord.push_back(a);
      for (auto &i : g[a]) {
        int b = graph_edges[i].a + graph_edges[i].b - a;
        if (!v2[b]) {
          parrent[b] = a;
          q.push(b);
          v2[b] = true;
        }
      }
    }

    for (auto &v : path) {
      dfs(v);
      sol = max(sol, bbpath[v]);
      value.push_back(under[v]);
    }

    ll total = 0;
    for (auto &i : edges) {
      total += graph_edges[i].cost;
    }

    ll cur = 0;
    for (int i = 1; i <= (int) edges.size(); i++) {
      cur += graph_edges[edges[i - 1]].cost;
      sum[i] = cur;
    }

    int y = (int) value.size();

    ll c1 = -INF, c2 = -INF;


    for (int r = 0; r < y; r++) {

      ll b1 = c1 + sum[r] + value[r];
      ll b2 = c2 + total + value[r] - sum[r];
      c1 = max(c1, value[r] - sum[r]);
      c2 = max(c2, sum[r] + value[r]);
      sol = max(sol, b1);
      sol = max(sol, b2);
    }
  }
  return sol;
}

signed main() {
  /// L < P

  ios::sync_with_stdio(0); cin.tie(0);

  ///freopen ("input2", "r", stdin);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    int j, c;
    cin >> j >> c;
    graph_edges[i].a = i;
    graph_edges[i].b = j;
    graph_edges[i].cost = c;
  }
  for (int i = 1; i <= n; i++) {
    g[graph_edges[i].a].push_back(i);
    g[graph_edges[i].b].push_back(i);
  }

  ll sol = 0;

  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      sol += solveComponent(i);
    }
  }

  cout << sol << "\n";

  return 0;
}

Compilation message

islands.cpp: In function 'll solveComponent(int)':
islands.cpp:117:9: warning: unused variable 'cost' [-Wunused-variable]
  117 |     int cost = graph_edges[index].cost;
      |         ^~~~

Subtask #1
18.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39500 KB Output is correct
2 Incorrect 18 ms 39476 KB Output isn't correct
3 Correct 18 ms 39428 KB Output is correct
4 Incorrect 18 ms 39500 KB Output isn't correct
5 Correct 17 ms 39516 KB Output is correct
6 Incorrect 18 ms 39508 KB Output isn't correct
7 Incorrect 17 ms 39464 KB Output isn't correct
8 Correct 18 ms 39500 KB Output is correct
9 Incorrect 17 ms 39416 KB Output isn't correct
10 Correct 17 ms 39500 KB Output is correct
11 Correct 18 ms 39472 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39612 KB Output is correct
2 Correct 18 ms 39552 KB Output is correct

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 39628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 40540 KB Output is correct
2 Correct 40 ms 42432 KB Output is correct
3 Incorrect 28 ms 41164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 43704 KB Output is correct
2 Correct 49 ms 45720 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 54396 KB Output is correct
2 Correct 99 ms 55332 KB Output is correct
3 Correct 117 ms 61528 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 63336 KB Output is correct
2 Correct 180 ms 81828 KB Output is correct
3 Correct 194 ms 80136 KB Output is correct
4 Correct 236 ms 99032 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 102588 KB Output is correct
2 Correct 878 ms 119464 KB Output is correct
3 Correct 263 ms 88640 KB Output is correct
4 Correct 350 ms 112024 KB Output is correct
5 Correct 334 ms 111040 KB Output is correct
6 Incorrect 1111 ms 104148 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 314 ms 93992 KB Output isn't correct
2 Halted 0 ms 0 KB -