oj.uz

Submission #979583

# Submission time Handle Problem Language Result Execution time Memory
979583 2024-05-11T07:59:31 Z bubble_xd Swapping Cities (APIO20_swap) C++17
13 / 100
 331 ms 46992 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int nax = 300005;
const int K = 23;

int fa[nax], front[nax], back[nax], val[nax];
bool chain[nax];
int N, M, id;
vector<pair<int, pair<int, int>>> edges; // (W, index)
vector<int> G[nax];
int sp[nax][K], dep[nax];

int find(int x) {
  if (x == fa[x]) return x;
  fa[x] = find(fa[x]);
  return fa[x];
}

void dfs(int u, int f) {
  dep[u] = dep[f] + 1;
  sp[u][0] = f;
  for (int i = 1; i < K; i++) sp[u][i] = sp[sp[u][i - 1]][i - 1];
  for (auto child : G[u]) dfs(child, u);
}

int lca(int u, int v) {
  if (dep[v] >= dep[u]) swap(u, v);
  for (int i = K - 1; i >= 0; i--) if (dep[sp[u][i]] >= dep[v]) u = sp[u][i];
  if (u == v) return u;
  for (int i = K - 1; i >= 0; i--) if (dep[sp[u][i]] != dep[sp[v][i]]) u = sp[u][i], v = sp[v][i];
  return sp[u][0];
}
void init(int _N, int _M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  N = _N; M = _M;
  for (int i = 0; i < M; i++) 
    edges.push_back(make_pair(W[i], make_pair(U[i], V[i])));
  sort(edges.begin(), edges.end());
  for (int i = 0; i < nax; i++) fa[i] = i;
  for (int i = 1; i <= N; i++) {
    chain[i] = true;
    front[i] = back[i] = i;
  }
  id = N;
  for (int i = 0; i < M; i++) {
    int w = edges[i].first;
    int u = edges[i].second.first + 1;
    int v = edges[i].second.second + 1;

    int A = find(u), B = find(v);
    if (A == B) {
      if (chain[A]) {
        int new_id = ++id;
        fa[A] = new_id;
        val[new_id] = w;
        G[new_id].push_back(A);
      }
      continue;
    }
    int new_id = ++id;
    fa[A] = new_id;
    fa[B] = new_id;
    val[new_id] = w;
    G[new_id].push_back(A);
    G[new_id].push_back(B);
    if (chain[A] && chain[B]) {
      if (front[A] == v || back[A] == v) swap(A, B);
      // connect u -> v 
      // x -> u -> v -> y
      if (front[A] == u) swap(front[A], back[A]);
      if (back[B] == v) swap(front[B], back[B]);
      if (back[A] == u && front[B] == v) {
        chain[new_id] = true;
        front[new_id] = front[A];
        back[new_id] = back[B];
      }
    }
  }
  dfs(id, 0);
}

int getMinimumFuelCapacity(int X, int Y) {
  X++; Y++;
  int l = lca(X, Y);
  if (!chain[l]) return val[l];
  for (int i = K - 1; i >= 0; i--) {
    if (sp[l][i] && chain[sp[l][i]]) {
      l = sp[l][i];
    }
  }
  if (l == id) return -1;
  return val[sp[l][0]];
}

// #include "grader.cpp"

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 5 ms 15704 KB Output is correct
9 Correct 78 ms 35532 KB Output is correct
10 Correct 94 ms 38600 KB Output is correct
11 Correct 92 ms 38736 KB Output is correct
12 Correct 109 ms 41156 KB Output is correct
13 Correct 82 ms 42696 KB Output is correct
14 Correct 86 ms 35508 KB Output is correct
15 Correct 242 ms 40516 KB Output is correct
16 Correct 240 ms 40344 KB Output is correct
17 Correct 271 ms 42840 KB Output is correct
18 Correct 323 ms 44636 KB Output is correct
19 Correct 106 ms 21500 KB Output is correct
20 Correct 266 ms 43968 KB Output is correct
21 Correct 238 ms 41696 KB Output is correct
22 Correct 248 ms 44240 KB Output is correct
23 Correct 297 ms 45864 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 246 ms 44628 KB Output is correct
4 Correct 233 ms 46856 KB Output is correct
5 Correct 246 ms 44892 KB Output is correct
6 Correct 245 ms 46992 KB Output is correct
7 Correct 258 ms 46920 KB Output is correct
8 Correct 331 ms 44828 KB Output is correct
9 Correct 236 ms 46900 KB Output is correct
10 Correct 230 ms 44420 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 5 ms 15704 KB Output is correct
9 Correct 3 ms 15704 KB Output is correct
10 Incorrect 4 ms 15708 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15704 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 4 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 5 ms 15704 KB Output is correct
10 Correct 78 ms 35532 KB Output is correct
11 Correct 94 ms 38600 KB Output is correct
12 Correct 92 ms 38736 KB Output is correct
13 Correct 109 ms 41156 KB Output is correct
14 Correct 82 ms 42696 KB Output is correct
15 Incorrect 4 ms 15708 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 5 ms 15704 KB Output is correct
9 Correct 78 ms 35532 KB Output is correct
10 Correct 94 ms 38600 KB Output is correct
11 Correct 92 ms 38736 KB Output is correct
12 Correct 109 ms 41156 KB Output is correct
13 Correct 82 ms 42696 KB Output is correct
14 Correct 86 ms 35508 KB Output is correct
15 Correct 242 ms 40516 KB Output is correct
16 Correct 240 ms 40344 KB Output is correct
17 Correct 271 ms 42840 KB Output is correct
18 Correct 323 ms 44636 KB Output is correct
19 Correct 246 ms 44628 KB Output is correct
20 Correct 233 ms 46856 KB Output is correct
21 Correct 246 ms 44892 KB Output is correct
22 Correct 245 ms 46992 KB Output is correct
23 Correct 258 ms 46920 KB Output is correct
24 Correct 331 ms 44828 KB Output is correct
25 Correct 236 ms 46900 KB Output is correct
26 Correct 230 ms 44420 KB Output is correct
27 Incorrect 4 ms 15708 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15704 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 4 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 5 ms 15704 KB Output is correct
10 Correct 78 ms 35532 KB Output is correct
11 Correct 94 ms 38600 KB Output is correct
12 Correct 92 ms 38736 KB Output is correct
13 Correct 109 ms 41156 KB Output is correct
14 Correct 82 ms 42696 KB Output is correct
15 Correct 86 ms 35508 KB Output is correct
16 Correct 242 ms 40516 KB Output is correct
17 Correct 240 ms 40344 KB Output is correct
18 Correct 271 ms 42840 KB Output is correct
19 Correct 323 ms 44636 KB Output is correct
20 Correct 246 ms 44628 KB Output is correct
21 Correct 233 ms 46856 KB Output is correct
22 Correct 246 ms 44892 KB Output is correct
23 Correct 245 ms 46992 KB Output is correct
24 Correct 258 ms 46920 KB Output is correct
25 Correct 331 ms 44828 KB Output is correct
26 Correct 236 ms 46900 KB Output is correct
27 Correct 230 ms 44420 KB Output is correct
28 Incorrect 4 ms 15708 KB Output isn't correct
29 Halted 0 ms 0 KB -