oj.uz

Submission #979593

# Submission time Handle Problem Language Result Execution time Memory
979593 2024-05-11T08:02:26 Z bubble_xd Swapping Cities (APIO20_swap) C++17
13 / 100
 281 ms 38720 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 (int child = 0; child < 2; child++) {
    dfs(G[u][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 11100 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 3 ms 11100 KB Output is correct
9 Correct 54 ms 28368 KB Output is correct
10 Correct 72 ms 29092 KB Output is correct
11 Correct 67 ms 29124 KB Output is correct
12 Correct 84 ms 31440 KB Output is correct
13 Correct 70 ms 32580 KB Output is correct
14 Correct 68 ms 28624 KB Output is correct
15 Correct 207 ms 31032 KB Output is correct
16 Correct 223 ms 31016 KB Output is correct
17 Correct 241 ms 33084 KB Output is correct
18 Correct 275 ms 34344 KB Output is correct
19 Correct 103 ms 16372 KB Output is correct
20 Correct 202 ms 34036 KB Output is correct
21 Correct 208 ms 32308 KB Output is correct
22 Correct 217 ms 34372 KB Output is correct
23 Correct 281 ms 35644 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 220 ms 36296 KB Output is correct
4 Correct 215 ms 38704 KB Output is correct
5 Correct 267 ms 36736 KB Output is correct
6 Correct 232 ms 38688 KB Output is correct
7 Correct 227 ms 38720 KB Output is correct
8 Correct 235 ms 36404 KB Output is correct
9 Correct 215 ms 38704 KB Output is correct
10 Correct 228 ms 36228 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 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 3 ms 11100 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 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 11100 KB Output is correct
9 Correct 3 ms 11100 KB Output is correct
10 Correct 54 ms 28368 KB Output is correct
11 Correct 72 ms 29092 KB Output is correct
12 Correct 67 ms 29124 KB Output is correct
13 Correct 84 ms 31440 KB Output is correct
14 Correct 70 ms 32580 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 11100 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 3 ms 11100 KB Output is correct
9 Correct 54 ms 28368 KB Output is correct
10 Correct 72 ms 29092 KB Output is correct
11 Correct 67 ms 29124 KB Output is correct
12 Correct 84 ms 31440 KB Output is correct
13 Correct 70 ms 32580 KB Output is correct
14 Correct 68 ms 28624 KB Output is correct
15 Correct 207 ms 31032 KB Output is correct
16 Correct 223 ms 31016 KB Output is correct
17 Correct 241 ms 33084 KB Output is correct
18 Correct 275 ms 34344 KB Output is correct
19 Correct 220 ms 36296 KB Output is correct
20 Correct 215 ms 38704 KB Output is correct
21 Correct 267 ms 36736 KB Output is correct
22 Correct 232 ms 38688 KB Output is correct
23 Correct 227 ms 38720 KB Output is correct
24 Correct 235 ms 36404 KB Output is correct
25 Correct 215 ms 38704 KB Output is correct
26 Correct 228 ms 36228 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 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 11100 KB Output is correct
9 Correct 3 ms 11100 KB Output is correct
10 Correct 54 ms 28368 KB Output is correct
11 Correct 72 ms 29092 KB Output is correct
12 Correct 67 ms 29124 KB Output is correct
13 Correct 84 ms 31440 KB Output is correct
14 Correct 70 ms 32580 KB Output is correct
15 Correct 68 ms 28624 KB Output is correct
16 Correct 207 ms 31032 KB Output is correct
17 Correct 223 ms 31016 KB Output is correct
18 Correct 241 ms 33084 KB Output is correct
19 Correct 275 ms 34344 KB Output is correct
20 Correct 220 ms 36296 KB Output is correct
21 Correct 215 ms 38704 KB Output is correct
22 Correct 267 ms 36736 KB Output is correct
23 Correct 232 ms 38688 KB Output is correct
24 Correct 227 ms 38720 KB Output is correct
25 Correct 235 ms 36404 KB Output is correct
26 Correct 215 ms 38704 KB Output is correct
27 Correct 228 ms 36228 KB Output is correct
28 Incorrect 2 ms 11100 KB Output isn't correct
29 Halted 0 ms 0 KB -