oj.uz

답안 #428792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428792 2021-06-15T14:32:27 Z Hegdahl 자매 도시 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -