oj.uz

Submission #428832

# Submission time Handle Problem Language Result Execution time Memory
428832 2021-06-15T14:45:23 Z Hegdahl Swapping Cities (APIO20_swap) C++17
13 / 100
 491 ms 42120 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define ar array

using namespace std;

const int mxN = 4*2e5;

int deg[mxN], boss[mxN], lk[mxN], rk[mxN], ndw[mxN], can_pass[mxN], nxt;

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

void unite(int i, int j, int w) {
  bool tri = ++deg[i] >= 3 || ++deg[j] >= 3;

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

  lk[nxt] = i;
  rk[nxt] = j;
  can_pass[nxt] = tri || can_pass[i] || can_pass[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]);

  for (int i = 1; i < n; ++i)
    assert(find(i) == find(0));

  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 (!can_pass[up[i][lvl]])
      i = up[i][lvl];

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

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

  return ndw[i];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9700 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Correct 6 ms 9892 KB Output is correct
6 Correct 6 ms 9916 KB Output is correct
7 Correct 6 ms 9932 KB Output is correct
8 Correct 6 ms 9928 KB Output is correct
9 Correct 80 ms 27332 KB Output is correct
10 Correct 102 ms 31344 KB Output is correct
11 Correct 93 ms 30916 KB Output is correct
12 Correct 97 ms 32028 KB Output is correct
13 Correct 105 ms 33660 KB Output is correct
14 Correct 97 ms 27580 KB Output is correct
15 Correct 289 ms 32896 KB Output is correct
16 Correct 280 ms 32388 KB Output is correct
17 Correct 294 ms 33592 KB Output is correct
18 Correct 415 ms 35140 KB Output is correct
19 Correct 137 ms 18264 KB Output is correct
20 Correct 288 ms 34140 KB Output is correct
21 Correct 282 ms 33612 KB Output is correct
22 Correct 300 ms 34824 KB Output is correct
23 Correct 491 ms 36388 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 424 ms 39372 KB Output is correct
4 Correct 427 ms 42120 KB Output is correct
5 Correct 442 ms 41700 KB Output is correct
6 Correct 441 ms 42016 KB Output is correct
7 Correct 432 ms 41920 KB Output is correct
8 Correct 464 ms 40872 KB Output is correct
9 Correct 423 ms 41700 KB Output is correct
10 Correct 450 ms 40632 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9700 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Correct 6 ms 9892 KB Output is correct
6 Correct 6 ms 9916 KB Output is correct
7 Correct 6 ms 9932 KB Output is correct
8 Correct 6 ms 9928 KB Output is correct
9 Correct 6 ms 9700 KB Output is correct
10 Incorrect 6 ms 9932 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9700 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 5 ms 9804 KB Output is correct
6 Correct 6 ms 9892 KB Output is correct
7 Correct 6 ms 9916 KB Output is correct
8 Correct 6 ms 9932 KB Output is correct
9 Correct 6 ms 9928 KB Output is correct
10 Correct 80 ms 27332 KB Output is correct
11 Correct 102 ms 31344 KB Output is correct
12 Correct 93 ms 30916 KB Output is correct
13 Correct 97 ms 32028 KB Output is correct
14 Correct 105 ms 33660 KB Output is correct
15 Incorrect 6 ms 9932 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9700 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Correct 6 ms 9892 KB Output is correct
6 Correct 6 ms 9916 KB Output is correct
7 Correct 6 ms 9932 KB Output is correct
8 Correct 6 ms 9928 KB Output is correct
9 Correct 80 ms 27332 KB Output is correct
10 Correct 102 ms 31344 KB Output is correct
11 Correct 93 ms 30916 KB Output is correct
12 Correct 97 ms 32028 KB Output is correct
13 Correct 105 ms 33660 KB Output is correct
14 Correct 97 ms 27580 KB Output is correct
15 Correct 289 ms 32896 KB Output is correct
16 Correct 280 ms 32388 KB Output is correct
17 Correct 294 ms 33592 KB Output is correct
18 Correct 415 ms 35140 KB Output is correct
19 Correct 424 ms 39372 KB Output is correct
20 Correct 427 ms 42120 KB Output is correct
21 Correct 442 ms 41700 KB Output is correct
22 Correct 441 ms 42016 KB Output is correct
23 Correct 432 ms 41920 KB Output is correct
24 Correct 464 ms 40872 KB Output is correct
25 Correct 423 ms 41700 KB Output is correct
26 Correct 450 ms 40632 KB Output is correct
27 Incorrect 6 ms 9932 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9700 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 5 ms 9804 KB Output is correct
6 Correct 6 ms 9892 KB Output is correct
7 Correct 6 ms 9916 KB Output is correct
8 Correct 6 ms 9932 KB Output is correct
9 Correct 6 ms 9928 KB Output is correct
10 Correct 80 ms 27332 KB Output is correct
11 Correct 102 ms 31344 KB Output is correct
12 Correct 93 ms 30916 KB Output is correct
13 Correct 97 ms 32028 KB Output is correct
14 Correct 105 ms 33660 KB Output is correct
15 Correct 97 ms 27580 KB Output is correct
16 Correct 289 ms 32896 KB Output is correct
17 Correct 280 ms 32388 KB Output is correct
18 Correct 294 ms 33592 KB Output is correct
19 Correct 415 ms 35140 KB Output is correct
20 Correct 424 ms 39372 KB Output is correct
21 Correct 427 ms 42120 KB Output is correct
22 Correct 442 ms 41700 KB Output is correct
23 Correct 441 ms 42016 KB Output is correct
24 Correct 432 ms 41920 KB Output is correct
25 Correct 464 ms 40872 KB Output is correct
26 Correct 423 ms 41700 KB Output is correct
27 Correct 450 ms 40632 KB Output is correct
28 Incorrect 6 ms 9932 KB Output isn't correct
29 Halted 0 ms 0 KB -