oj.uz

답안 #961422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961422 2024-04-12T05:00:36 Z kilkuwu 자매 도시 (APIO20_swap) C++17
7 / 100
 504 ms 524288 KB 
#include "swap.h"

#include <bits/stdc++.h>

template <typename T>
inline bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}

template <typename T>
inline bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}

constexpr int mxM = 200'000;
constexpr int mxN = 100'000;
constexpr int LOG = 20;
constexpr int inf = 1e9 + 7;

struct Edge {
  int u, v, w;

  bool operator<(const Edge& rhs) const {
    return w < rhs.w;
  }

  inline int other(int x) { return u ^ v ^ x; }
};

Edge edges[mxM];
std::vector<std::pair<int, int>> adj[mxN];

int up[LOG][mxN];
int vv[LOG][mxN];
int dep[mxN];

int num_nodes;

std::pair<int, int> par[mxN + mxM];
// we need to find first cycle and first three;

std::pair<int, int> find(int u) {
  if (par[u].first == -1) {
    return {u, par[u].second};
  }

  auto pu = find(par[u].first);
  pu.second = std::min(pu.second, par[u].second);

  return par[u] = pu;
}

void merge(int u, int v, int w) {
  adj[u].emplace_back(w, v);
  adj[v].emplace_back(w, u);

  auto pu = find(u), pv = find(v);

  if (adj[u].size() > 2 || adj[v].size() > 2) {
    ckmin(par[num_nodes].second, w);
  }

  if (pu == pv) {
    ckmin(par[num_nodes].second, w);
  }

  par[pu.first].first = par[pv.first].first = num_nodes;

  num_nodes++;
}

void dfs(int u) {
  for (auto [w, v] : adj[u]) {
    if (v == up[0][u]) continue;
    dep[v] = dep[u] + 1;
    up[0][v] = u;
    vv[0][v] = w;
    dfs(v);
  } 
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  
  for (int i = 0; i < N + M; i++) {
    par[i] = {-1, inf};
  }

  num_nodes = N;
  for (int i = 0; i < M; i++) {
    edges[i] = {U[i], V[i], W[i]};
  }

  std::sort(edges, edges + M);

  for (int i = 0; i < M; i++) {
    auto [u, v, w] = edges[i];
    merge(u, v, w);
  }

  dfs(0);

  for (int k = 0; k + 1 < LOG; k++) {
    for (int i = 0; i < N; i++) {
      up[k + 1][i] = up[k][up[k][i]];
      vv[k + 1][i] = std::max(vv[k][i], vv[k][up[k][i]]);
    }
  }
}

int max_path(int u, int v) {
  if (dep[u] > dep[v]) std::swap(u, v);
  int d = dep[v] - dep[u];
  int ans = 0;
  for (int k = 0; k < LOG; k++) {
    if (d >> k & 1) {
      ckmax(ans, vv[k][v]);
      v = up[k][v];
    }
  }

  if (u == v) return ans;

  for (int k = LOG - 1; k >= 0; k--) {
    if (up[k][u] != up[k][v]) {
      ckmax(ans, vv[k][u]);
      ckmax(ans, vv[k][v]);
      u = up[k][u];
      v = up[k][v];
    }
  }

  ckmax(ans, vv[0][u]);
  ckmax(ans, vv[0][v]);

  return ans;
}

int getMinimumFuelCapacity(int X, int Y) {
  int ans = std::min(find(X).second, find(Y).second);
  ans = std::max(ans, max_path(X, Y));
  return ans <= 1e9 ? ans : -1; 
}

#ifdef LOCAL

#endif

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 52 ms 30032 KB Output is correct
10 Correct 59 ms 33108 KB Output is correct
11 Correct 56 ms 32428 KB Output is correct
12 Correct 60 ms 33356 KB Output is correct
13 Correct 69 ms 34640 KB Output is correct
14 Correct 72 ms 29496 KB Output is correct
15 Correct 199 ms 34644 KB Output is correct
16 Correct 228 ms 33116 KB Output is correct
17 Correct 182 ms 36556 KB Output is correct
18 Correct 256 ms 35256 KB Output is correct
19 Runtime error 504 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 124 ms 33388 KB Output is correct
4 Correct 131 ms 38220 KB Output is correct
5 Correct 128 ms 38460 KB Output is correct
6 Correct 121 ms 38148 KB Output is correct
7 Correct 144 ms 37556 KB Output is correct
8 Correct 118 ms 38004 KB Output is correct
9 Correct 111 ms 37448 KB Output is correct
10 Correct 119 ms 37008 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Runtime error 289 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 52 ms 30032 KB Output is correct
10 Correct 59 ms 33108 KB Output is correct
11 Correct 56 ms 32428 KB Output is correct
12 Correct 60 ms 33356 KB Output is correct
13 Correct 69 ms 34640 KB Output is correct
14 Correct 72 ms 29496 KB Output is correct
15 Correct 199 ms 34644 KB Output is correct
16 Correct 228 ms 33116 KB Output is correct
17 Correct 182 ms 36556 KB Output is correct
18 Correct 256 ms 35256 KB Output is correct
19 Correct 124 ms 33388 KB Output is correct
20 Correct 131 ms 38220 KB Output is correct
21 Correct 128 ms 38460 KB Output is correct
22 Correct 121 ms 38148 KB Output is correct
23 Correct 144 ms 37556 KB Output is correct
24 Correct 118 ms 38004 KB Output is correct
25 Correct 111 ms 37448 KB Output is correct
26 Correct 119 ms 37008 KB Output is correct
27 Correct 4 ms 19036 KB Output is correct
28 Incorrect 3 ms 19032 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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