oj.uz

Submission #979588

# Submission time Handle Problem Language Result Execution time Memory
979588 2024-05-11T08:01:20 Z bubble_xd Swapping Cities (APIO20_swap) C++17
13 / 100
 305 ms 38860 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)
int G[nax][2], 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) {
  if (!u) return;
  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][0] = A;
      }
      continue;
    }
    int new_id = ++id;
    fa[A] = new_id;
    fa[B] = new_id;
    val[new_id] = w;
    G[new_id][0] = A;
    G[new_id][1] = 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]];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11096 KB Output is correct
9 Correct 53 ms 28376 KB Output is correct
10 Correct 69 ms 29096 KB Output is correct
11 Correct 66 ms 29128 KB Output is correct
12 Correct 70 ms 31176 KB Output is correct
13 Correct 74 ms 32472 KB Output is correct
14 Correct 64 ms 28736 KB Output is correct
15 Correct 236 ms 31060 KB Output is correct
16 Correct 206 ms 30876 KB Output is correct
17 Correct 216 ms 33064 KB Output is correct
18 Correct 305 ms 34268 KB Output is correct
19 Correct 105 ms 16400 KB Output is correct
20 Correct 208 ms 34120 KB Output is correct
21 Correct 208 ms 32128 KB Output is correct
22 Correct 232 ms 34348 KB Output is correct
23 Correct 298 ms 35672 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 219 ms 36460 KB Output is correct
4 Correct 281 ms 38736 KB Output is correct
5 Correct 232 ms 36700 KB Output is correct
6 Correct 215 ms 38584 KB Output is correct
7 Correct 245 ms 38860 KB Output is correct
8 Correct 210 ms 36464 KB Output is correct
9 Correct 237 ms 38724 KB Output is correct
10 Correct 211 ms 36236 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 2 ms 11096 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11096 KB Output is correct
10 Correct 53 ms 28376 KB Output is correct
11 Correct 69 ms 29096 KB Output is correct
12 Correct 66 ms 29128 KB Output is correct
13 Correct 70 ms 31176 KB Output is correct
14 Correct 74 ms 32472 KB Output is correct
15 Incorrect 2 ms 11100 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11096 KB Output is correct
9 Correct 53 ms 28376 KB Output is correct
10 Correct 69 ms 29096 KB Output is correct
11 Correct 66 ms 29128 KB Output is correct
12 Correct 70 ms 31176 KB Output is correct
13 Correct 74 ms 32472 KB Output is correct
14 Correct 64 ms 28736 KB Output is correct
15 Correct 236 ms 31060 KB Output is correct
16 Correct 206 ms 30876 KB Output is correct
17 Correct 216 ms 33064 KB Output is correct
18 Correct 305 ms 34268 KB Output is correct
19 Correct 219 ms 36460 KB Output is correct
20 Correct 281 ms 38736 KB Output is correct
21 Correct 232 ms 36700 KB Output is correct
22 Correct 215 ms 38584 KB Output is correct
23 Correct 245 ms 38860 KB Output is correct
24 Correct 210 ms 36464 KB Output is correct
25 Correct 237 ms 38724 KB Output is correct
26 Correct 211 ms 36236 KB Output is correct
27 Incorrect 2 ms 11100 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 2 ms 11096 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11096 KB Output is correct
10 Correct 53 ms 28376 KB Output is correct
11 Correct 69 ms 29096 KB Output is correct
12 Correct 66 ms 29128 KB Output is correct
13 Correct 70 ms 31176 KB Output is correct
14 Correct 74 ms 32472 KB Output is correct
15 Correct 64 ms 28736 KB Output is correct
16 Correct 236 ms 31060 KB Output is correct
17 Correct 206 ms 30876 KB Output is correct
18 Correct 216 ms 33064 KB Output is correct
19 Correct 305 ms 34268 KB Output is correct
20 Correct 219 ms 36460 KB Output is correct
21 Correct 281 ms 38736 KB Output is correct
22 Correct 232 ms 36700 KB Output is correct
23 Correct 215 ms 38584 KB Output is correct
24 Correct 245 ms 38860 KB Output is correct
25 Correct 210 ms 36464 KB Output is correct
26 Correct 237 ms 38724 KB Output is correct
27 Correct 211 ms 36236 KB Output is correct
28 Incorrect 2 ms 11100 KB Output isn't correct
29 Halted 0 ms 0 KB -