oj.uz

Submission #744992

# Submission time Handle Problem Language Result Execution time Memory
744992 2023-05-19T09:36:14 Z arush_agu Swapping Cities (APIO20_swap) C++17
30 / 100
 2000 ms 20108 KB 
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e9;
const ld EPS = 1e-9;

int n, m;
vl u, v, w;
vvll adj;

bool sub1 = 0;
int mx_w;

bool sub2 = 0;
vll w_sort;

struct DSU {
  int nn;
  vi par, sz;

  void init(int nnn) {
    nn = nnn;
    par = vi(nn, -1); sz = vi(nn, 1);
  }

  int find(int x) {
    if (par[x] == -1) return x;
    return par[x] = find(par[x]);
  }

  void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    par[y] = x;
    sz[x] += sz[y];
  }
} dsu;

void init(int nn, int mm, vi uu, vi vv, vi ww) {
  n = nn, m = mm;
  for (int &x : uu) u.push_back(x);
  for (int &x : vv) v.push_back(x);
  for (int &x : ww) w.push_back(x);
  adj = vvll(n);
  for (int i=0; i<m; i++) {
    adj[u[i]].push_back({v[i], w[i]});
    adj[v[i]].push_back({u[i], w[i]});
  }

  sub1 = 1;
  for (int i=0; i<m; i++) if (adj[i].size() > 2) {
    sub1 = 0; break;
  }
  if (sub1) mx_w = *max_element(all(w));

  sub2 = 1;
  if (m != n - 1) sub2 = 0;
  for (int i=0; i<m; i++) if (u[i] != 0) {
    sub2 = 0;
    break;
  }
  if (sub2) {
    w_sort = vll(m); for (int i=0; i<m; i++) w_sort[i] = {w[i], v[i]};
    sort(all(w_sort));
  }
}

int getMinimumFuelCapacity(int x, int y) {
  if (sub1) {
    if (m == n - 1) return -1;
    assert(m == n);
    return mx_w;
  }

  if (sub2) {
    if (x > y) swap(x, y);
    if (x == 0) {
      if (y == w_sort[0].second || y == w_sort[1].second)
        return w_sort[2].first;
      return max(adj[y][0].second, w_sort[1].first);
    }

    if (adj[x][0].second > adj[y][0].second) swap(x, y);
    if (w_sort[0].first == adj[x][0].second && w_sort[1].first == adj[y][0].second) return w_sort[2].first;
    return adj[y][0].second;
  }

  auto check = [&](int mid) {
    dsu.init(n);
    vvi nadj(n);
    for (int i=0; i<m; i++) if (w[i] <= mid) {
      dsu.merge(u[i], v[i]);
      nadj[u[i]].push_back(v[i]);
      nadj[v[i]].push_back(u[i]);
    }

    if (dsu.find(x) != dsu.find(y)) return 0;

    vi in_cc; for (int i=0; i<n; i++) if (dsu.find(x) == dsu.find(i)) {
      in_cc.push_back(i);
    }

    int cnt = in_cc.size();
    int cnt_1deg = 0, cnt_2deg = 0;
    for (int &node : in_cc) {
      if (nadj[node].size() == 1) cnt_1deg++;
      if (nadj[node].size() == 2) cnt_2deg++;
    }

    if (cnt_1deg == 2 && cnt_2deg == cnt - 2) return 0;
    return 1;
  };

  ll l = 1, r = INF, ans = INF;
  while (l <= r) {
    ll mid = (l + r) / 2;
    if (check(mid)) {
      ans = mid;
      r = mid - 1;
    } else l = mid + 1;
  }
  return ans;
}

#ifdef DEBUG
void solve() {
  int n, m; cin >> n >> m;
  vi u(m), v(m), w(m);
  for (int i=0; i<m; i++) {
    cin >> u[i] >> v[i] >> w[i];
  }

  init(n, m, u, v, w);

  int q; cin >> q;
  while (q--) {
    int x, y; cin >> x >> y;
    cout << getMinimumFuelCapacity(x, y) << "\n";
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  clock_t start = clock();

  int test_cases = 1;
  /* cin >> test_cases; */

  while (test_cases--)
    solve();

  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
  return 0;
}
#endif

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 41 ms 9944 KB Output is correct
10 Correct 50 ms 11976 KB Output is correct
11 Correct 49 ms 11848 KB Output is correct
12 Correct 53 ms 12596 KB Output is correct
13 Correct 58 ms 12536 KB Output is correct
14 Correct 46 ms 10048 KB Output is correct
15 Correct 104 ms 13864 KB Output is correct
16 Correct 101 ms 13608 KB Output is correct
17 Correct 106 ms 14376 KB Output is correct
18 Correct 106 ms 14376 KB Output is correct
19 Correct 49 ms 5704 KB Output is correct
20 Correct 102 ms 15264 KB Output is correct
21 Correct 102 ms 15068 KB Output is correct
22 Correct 105 ms 15908 KB Output is correct
23 Correct 104 ms 15892 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 103 ms 15920 KB Output is correct
4 Correct 106 ms 16420 KB Output is correct
5 Correct 110 ms 16412 KB Output is correct
6 Correct 110 ms 16492 KB Output is correct
7 Correct 110 ms 16620 KB Output is correct
8 Correct 111 ms 16016 KB Output is correct
9 Correct 114 ms 16444 KB Output is correct
10 Correct 105 ms 16036 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 17 ms 468 KB Output is correct
11 Correct 18 ms 468 KB Output is correct
12 Correct 17 ms 488 KB Output is correct
13 Correct 15 ms 468 KB Output is correct
14 Correct 16 ms 472 KB Output is correct
15 Correct 21 ms 436 KB Output is correct
16 Correct 20 ms 504 KB Output is correct
17 Correct 19 ms 468 KB Output is correct
18 Correct 24 ms 444 KB Output is correct
19 Correct 12 ms 484 KB Output is correct
20 Correct 18 ms 504 KB Output is correct
21 Correct 17 ms 528 KB Output is correct
22 Correct 7 ms 444 KB Output is correct
23 Correct 13 ms 468 KB Output is correct
24 Correct 21 ms 468 KB Output is correct
25 Correct 22 ms 568 KB Output is correct
26 Correct 23 ms 596 KB Output is correct
27 Correct 17 ms 440 KB Output is correct
28 Correct 20 ms 596 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 41 ms 9944 KB Output is correct
11 Correct 50 ms 11976 KB Output is correct
12 Correct 49 ms 11848 KB Output is correct
13 Correct 53 ms 12596 KB Output is correct
14 Correct 58 ms 12536 KB Output is correct
15 Correct 17 ms 468 KB Output is correct
16 Correct 18 ms 468 KB Output is correct
17 Correct 17 ms 488 KB Output is correct
18 Correct 15 ms 468 KB Output is correct
19 Correct 16 ms 472 KB Output is correct
20 Correct 21 ms 436 KB Output is correct
21 Correct 20 ms 504 KB Output is correct
22 Correct 19 ms 468 KB Output is correct
23 Correct 24 ms 444 KB Output is correct
24 Correct 12 ms 484 KB Output is correct
25 Correct 18 ms 504 KB Output is correct
26 Correct 17 ms 528 KB Output is correct
27 Correct 7 ms 444 KB Output is correct
28 Correct 13 ms 468 KB Output is correct
29 Correct 21 ms 468 KB Output is correct
30 Correct 22 ms 568 KB Output is correct
31 Correct 23 ms 596 KB Output is correct
32 Correct 17 ms 440 KB Output is correct
33 Correct 20 ms 596 KB Output is correct
34 Correct 66 ms 3228 KB Output is correct
35 Execution timed out 2055 ms 20108 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 41 ms 9944 KB Output is correct
10 Correct 50 ms 11976 KB Output is correct
11 Correct 49 ms 11848 KB Output is correct
12 Correct 53 ms 12596 KB Output is correct
13 Correct 58 ms 12536 KB Output is correct
14 Correct 46 ms 10048 KB Output is correct
15 Correct 104 ms 13864 KB Output is correct
16 Correct 101 ms 13608 KB Output is correct
17 Correct 106 ms 14376 KB Output is correct
18 Correct 106 ms 14376 KB Output is correct
19 Correct 103 ms 15920 KB Output is correct
20 Correct 106 ms 16420 KB Output is correct
21 Correct 110 ms 16412 KB Output is correct
22 Correct 110 ms 16492 KB Output is correct
23 Correct 110 ms 16620 KB Output is correct
24 Correct 111 ms 16016 KB Output is correct
25 Correct 114 ms 16444 KB Output is correct
26 Correct 105 ms 16036 KB Output is correct
27 Correct 17 ms 468 KB Output is correct
28 Correct 18 ms 468 KB Output is correct
29 Correct 17 ms 488 KB Output is correct
30 Correct 15 ms 468 KB Output is correct
31 Correct 16 ms 472 KB Output is correct
32 Correct 21 ms 436 KB Output is correct
33 Correct 20 ms 504 KB Output is correct
34 Correct 19 ms 468 KB Output is correct
35 Correct 24 ms 444 KB Output is correct
36 Correct 66 ms 3228 KB Output is correct
37 Execution timed out 2055 ms 20108 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 41 ms 9944 KB Output is correct
11 Correct 50 ms 11976 KB Output is correct
12 Correct 49 ms 11848 KB Output is correct
13 Correct 53 ms 12596 KB Output is correct
14 Correct 58 ms 12536 KB Output is correct
15 Correct 46 ms 10048 KB Output is correct
16 Correct 104 ms 13864 KB Output is correct
17 Correct 101 ms 13608 KB Output is correct
18 Correct 106 ms 14376 KB Output is correct
19 Correct 106 ms 14376 KB Output is correct
20 Correct 103 ms 15920 KB Output is correct
21 Correct 106 ms 16420 KB Output is correct
22 Correct 110 ms 16412 KB Output is correct
23 Correct 110 ms 16492 KB Output is correct
24 Correct 110 ms 16620 KB Output is correct
25 Correct 111 ms 16016 KB Output is correct
26 Correct 114 ms 16444 KB Output is correct
27 Correct 105 ms 16036 KB Output is correct
28 Correct 17 ms 468 KB Output is correct
29 Correct 18 ms 468 KB Output is correct
30 Correct 17 ms 488 KB Output is correct
31 Correct 15 ms 468 KB Output is correct
32 Correct 16 ms 472 KB Output is correct
33 Correct 21 ms 436 KB Output is correct
34 Correct 20 ms 504 KB Output is correct
35 Correct 19 ms 468 KB Output is correct
36 Correct 24 ms 444 KB Output is correct
37 Correct 66 ms 3228 KB Output is correct
38 Execution timed out 2055 ms 20108 KB Time limit exceeded
39 Halted 0 ms 0 KB -