oj.uz

Submission #428792

# Submission time Handle Problem Language Result Execution time Memory
428792 2021-06-15T14:32:27 Z Hegdahl Swapping Cities (APIO20_swap) C++17
6 / 100
 429 ms 37140 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define ar array

using namespace std;

const int mxN = 3*2e5;

int boss[mxN], lk[mxN], rk[mxN], ndw[mxN], has_cycle[mxN], nxt;

int find(int i) {
  return i == boss[i] ? i : boss[i] = find(boss[i]);
}

void unite(int i, int j, int w) {
  i = find(i), j = find(j);
  if (i == j) {
    if (has_cycle[i]) return;
    lk[nxt] = i;
    has_cycle[nxt] = 1;
    ndw[nxt] = w;
    boss[i] = nxt++;
    return;
  }

  lk[nxt] = i;
  rk[nxt] = j;
  has_cycle[nxt] = has_cycle[i] || has_cycle[j];
  ndw[nxt] = w;
  boss[i] = boss[j] = nxt++;
}

int up[mxN][20], depth[mxN];
void dfs(int cur, int prv, int d) {
  depth[cur] = d;
  up[cur][0] = prv;
  for (int lvl = 0; lvl < 19; ++lvl)
    up[cur][lvl+1] = up[up[cur][lvl]][lvl];

  if (lk[cur] != -1) dfs(lk[cur], cur, d+1);
  if (rk[cur] != -1) dfs(rk[cur], cur, d+1);
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
  iota(boss, boss+mxN, 0);
  fill(lk, lk+mxN, -1);
  fill(rk, rk+mxN, -1);
  nxt = n;

  vector<int> s(m);
  iota(s.begin(), s.end(), 0);
  sort(s.begin(), s.end(), [&](int i, int j) { return w[i] < w[j]; });
  for (int i : s) unite(u[i], v[i], w[i]);

  dfs(find(0), find(0), 0);
}

int getMinimumFuelCapacity(int i, int j) {
  if (depth[i] > depth[j]) swap(i, j);

  for (int lvl = 19; lvl >= 0; --lvl)
    if (depth[up[j][lvl]] >= depth[i])
      j = up[j][lvl];

  for (int lvl = 19; lvl >= 0; --lvl)
    if (up[i][lvl] != up[j][lvl])
      up[i][lvl] = up[j][lvl];

  if (i != j) i = up[i][0], j = up[j][0];

  assert(i == j);

  for (int lvl = 19; lvl >= 0; --lvl)
    if (!has_cycle[up[i][lvl]])
      i = up[i][lvl];

  if (!has_cycle[i]) i = up[i][0];

  if (!has_cycle[i]) return -1;

  return ndw[i];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 6 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 74 ms 24644 KB Output is correct
10 Correct 91 ms 28556 KB Output is correct
11 Correct 96 ms 28136 KB Output is correct
12 Correct 113 ms 29380 KB Output is correct
13 Correct 103 ms 31020 KB Output is correct
14 Correct 94 ms 25020 KB Output is correct
15 Correct 300 ms 32528 KB Output is correct
16 Correct 268 ms 31932 KB Output is correct
17 Correct 323 ms 33220 KB Output is correct
18 Correct 386 ms 34868 KB Output is correct
19 Correct 131 ms 15796 KB Output is correct
20 Correct 278 ms 33460 KB Output is correct
21 Correct 276 ms 33044 KB Output is correct
22 Correct 288 ms 34464 KB Output is correct
23 Correct 429 ms 36044 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Incorrect 350 ms 37140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 6 ms 7500 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 74 ms 24644 KB Output is correct
11 Correct 91 ms 28556 KB Output is correct
12 Correct 96 ms 28136 KB Output is correct
13 Correct 113 ms 29380 KB Output is correct
14 Correct 103 ms 31020 KB Output is correct
15 Incorrect 5 ms 7500 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 6 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 74 ms 24644 KB Output is correct
10 Correct 91 ms 28556 KB Output is correct
11 Correct 96 ms 28136 KB Output is correct
12 Correct 113 ms 29380 KB Output is correct
13 Correct 103 ms 31020 KB Output is correct
14 Correct 94 ms 25020 KB Output is correct
15 Correct 300 ms 32528 KB Output is correct
16 Correct 268 ms 31932 KB Output is correct
17 Correct 323 ms 33220 KB Output is correct
18 Correct 386 ms 34868 KB Output is correct
19 Incorrect 350 ms 37140 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 6 ms 7500 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 74 ms 24644 KB Output is correct
11 Correct 91 ms 28556 KB Output is correct
12 Correct 96 ms 28136 KB Output is correct
13 Correct 113 ms 29380 KB Output is correct
14 Correct 103 ms 31020 KB Output is correct
15 Correct 94 ms 25020 KB Output is correct
16 Correct 300 ms 32528 KB Output is correct
17 Correct 268 ms 31932 KB Output is correct
18 Correct 323 ms 33220 KB Output is correct
19 Correct 386 ms 34868 KB Output is correct
20 Incorrect 350 ms 37140 KB Output isn't correct
21 Halted 0 ms 0 KB -