oj.uz

답안 #975759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975759 2024-05-05T20:08:46 Z OAleksa 자매 도시 (APIO20_swap) C++14
0 / 100
 2000 ms 9928 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 69;
vector<tuple<int, int, int>> edges;
int n, m, p[N], sz[N], dg, deg[N];
int root(int v) {
  if (p[v] == v)
    return v;
  return p[v] = root(p[v]);
}
void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w) {
  n = _n;
  m = _m;
  for (int i = 0;i < m;i++) {
    edges.push_back({w[i], u[i], v[i]});
    deg[u[i]]++;
    deg[v[i]]++;
  }
}

int getMinimumFuelCapacity(int x, int y) {
  int ans = -1;
  int l = 1, r = 10;
  auto check = [&](int mid) {
    for (int i = 0;i < n;i++) {
      p[i] = i;
      sz[i] = 1;
      deg[i] = 0;
    }
    for (int i = 0;i < m;i++) {
      int a, b, c;
      tie(c, a, b) = edges[i];
      if (c > mid)
        continue;
      deg[a]++;
      deg[b]++;
      int t = root(a);
      int tt = root(b);
      if (t != tt) {
        if (sz[t] < sz[tt])
          swap(t, tt);
        sz[t] += sz[tt];
        p[tt] = t;
      }
    }
    if (root(x) != root(y))
      return false;
    bool ok = 0, all = 1;
    for (int i = 0;i < n;i++) {
      if (root(i) == root(x)) {
        ok |= (deg[i] > 2);
        all &= (deg[i] == 2);
      }
    }
    return ok || all;
  };
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
      ans = mid;
      r = mid - 1;
    }
    else
      l = mid + 1;
  }
  return ans;
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

3 2
0 1 5
0 2 5
1
1 2

*/

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 448 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 21 ms 5836 KB Output is correct
10 Correct 26 ms 6672 KB Output is correct
11 Correct 26 ms 6612 KB Output is correct
12 Correct 28 ms 6868 KB Output is correct
13 Correct 27 ms 6980 KB Output is correct
14 Execution timed out 2008 ms 6096 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2025 ms 9928 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 448 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 21 ms 5836 KB Output is correct
11 Correct 26 ms 6672 KB Output is correct
12 Correct 26 ms 6612 KB Output is correct
13 Correct 28 ms 6868 KB Output is correct
14 Correct 27 ms 6980 KB Output is correct
15 Incorrect 1 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 448 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 21 ms 5836 KB Output is correct
10 Correct 26 ms 6672 KB Output is correct
11 Correct 26 ms 6612 KB Output is correct
12 Correct 28 ms 6868 KB Output is correct
13 Correct 27 ms 6980 KB Output is correct
14 Execution timed out 2008 ms 6096 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 21 ms 5836 KB Output is correct
11 Correct 26 ms 6672 KB Output is correct
12 Correct 26 ms 6612 KB Output is correct
13 Correct 28 ms 6868 KB Output is correct
14 Correct 27 ms 6980 KB Output is correct
15 Execution timed out 2008 ms 6096 KB Time limit exceeded
16 Halted 0 ms 0 KB -