oj.uz

Submission #744946

# Submission time Handle Problem Language Result Execution time Memory
744946 2023-05-19T08:45:06 Z arush_agu Swapping Cities (APIO20_swap) C++17
13 / 100
 110 ms 20420 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;

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;
  }
  assert(0);
}

#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 0 ms 212 KB Output is correct
3 Correct 1 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 43 ms 9920 KB Output is correct
10 Correct 50 ms 11976 KB Output is correct
11 Correct 53 ms 11980 KB Output is correct
12 Correct 54 ms 12480 KB Output is correct
13 Correct 52 ms 12496 KB Output is correct
14 Correct 46 ms 10048 KB Output is correct
15 Correct 98 ms 13856 KB Output is correct
16 Correct 99 ms 13552 KB Output is correct
17 Correct 104 ms 14368 KB Output is correct
18 Correct 100 ms 14364 KB Output is correct
19 Correct 50 ms 5712 KB Output is correct
20 Correct 103 ms 15296 KB Output is correct
21 Correct 103 ms 14904 KB Output is correct
22 Correct 104 ms 15788 KB Output is correct
23 Correct 105 ms 15692 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 0 ms 212 KB Output is correct
3 Correct 103 ms 15840 KB Output is correct
4 Correct 110 ms 16400 KB Output is correct
5 Correct 104 ms 16304 KB Output is correct
6 Correct 101 ms 20112 KB Output is correct
7 Correct 105 ms 20420 KB Output is correct
8 Correct 103 ms 19604 KB Output is correct
9 Correct 107 ms 20036 KB Output is correct
10 Correct 107 ms 19656 KB Output is correct

Subtask #3
0 / 17.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 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 Runtime error 1 ms 340 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 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 0 ms 212 KB Output is correct
3 Correct 1 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 43 ms 9920 KB Output is correct
10 Correct 50 ms 11976 KB Output is correct
11 Correct 53 ms 11980 KB Output is correct
12 Correct 54 ms 12480 KB Output is correct
13 Correct 52 ms 12496 KB Output is correct
14 Correct 46 ms 10048 KB Output is correct
15 Correct 98 ms 13856 KB Output is correct
16 Correct 99 ms 13552 KB Output is correct
17 Correct 104 ms 14368 KB Output is correct
18 Correct 100 ms 14364 KB Output is correct
19 Correct 103 ms 15840 KB Output is correct
20 Correct 110 ms 16400 KB Output is correct
21 Correct 104 ms 16304 KB Output is correct
22 Correct 101 ms 20112 KB Output is correct
23 Correct 105 ms 20420 KB Output is correct
24 Correct 103 ms 19604 KB Output is correct
25 Correct 107 ms 20036 KB Output is correct
26 Correct 107 ms 19656 KB Output is correct
27 Runtime error 2 ms 692 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -