oj.uz

Submission #985719

# Submission time Handle Problem Language Result Execution time Memory
985719 2024-05-18T15:00:44 Z yoav_s Swapping Cities (APIO20_swap) C++17
17 / 100
 2000 ms 22732 KB 
#include <bits/stdc++.h>
using namespace std;

typedef int ll;
typedef pair<ll,ll> p;
typedef pair<ll, p> tri;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<p> vp;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<vv> vvv;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef vector<vvvp> vvvvp;
#define double long double
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;

const ll mod = 1e9 + 7;
const ll INF = 1e18;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define loop(a) for (ll i = 0; i < a; i++)
#define setmin(a, b) a = min(a, b)
#define setmax(a, b) a = max(a, b)
#define all(v) v.begin(), v.end()

#include "swap.h"
ll res = -1;
vvp graph;
ll maxW = -INF;
ll N;
v weightInflate;

ll getParent(ll i, v &dsuPar, v &times, ll time)
{
  if (times[i] > time) return i;
  return getParent(dsuPar[i], dsuPar, times, time);
}
v dsuParent, timeBecomeNotRoot, dsuSize, timeValid;
void init(int Nn, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  N = Nn;
  for (auto x : W) weightInflate.pb(x);
  sort(all(weightInflate));
  weightInflate.erase(unique(all(weightInflate)), weightInflate.end());
  map<ll, ll> weightShrink;
  for (ll i = 0; i < weightInflate.size(); i++) weightShrink[weightInflate[i]] = i;
  maxW = weightInflate.size() - 1;
  graph = vvp(N);
  for (ll i = 0; i < M; i++)
  {
    graph[U[i]].eb(V[i], weightShrink[W[i]]);
    graph[V[i]].eb(U[i], weightShrink[W[i]]);
  }
  dsuParent = v(N);
  timeBecomeNotRoot = v(N, INF);
  dsuSize = v(N, 1);
  timeValid = v(N, INF);
  for (ll i = 0; i < N; i++) dsuParent[i] = i;
  vtri edgesByW;
  for (ll i = 0; i < M; i++) edgesByW.eb(weightShrink[W[i]], p(U[i], V[i]));
  sort(all(edgesByW));
  v curDegree(N, 0);
  for (auto x : edgesByW)
  {
    ll l = x.s.f, r = x.s.s;
    ll p1 = getParent(l, dsuParent, timeBecomeNotRoot, x.f), p2 = getParent(r, dsuParent, timeBecomeNotRoot, x.f);
    if (p1 == p2)
    {
      timeValid[p1] = min(timeValid[p1], x.f);
      continue;
    }
    if (dsuSize[p1] < dsuSize[p2]) swap(p1, p2);
    dsuParent[p1] = p2;
    dsuSize[p2] += dsuSize[p1];
    timeBecomeNotRoot[p1] = x.f;
    curDegree[l]++; curDegree[r]++;
    if ((timeValid[p1] < INF || curDegree[l] >= 3 || curDegree[r] >= 3) && timeValid[p2] == INF) timeValid[p2] = x.f;
  }
}

int getMinimumFuelCapacity(int X, int Y) {
  ll mini = 0, maxi = maxW + 1;
  while (mini < maxi)
  {
    ll mid = (mini + maxi) / 2;
    ll p1 = getParent(X, dsuParent, timeBecomeNotRoot, mid), p2 = getParent(Y, dsuParent, timeBecomeNotRoot, mid);
    bool poss = (p1 == p2 && timeValid[p1] <= mid);
    if (poss)
    {
      maxi = mid;
    }
    else
    {
      mini = mid + 1;
    }
  }
  if (mini > maxW) return -1;
  return weightInflate[mini];
}
/*
int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));
  
  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  int Q;
  assert(1 == scanf("%d", &Q));

  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);
  
  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }
  
  return 0;
}
/**/

Compilation message

swap.cpp:142:1: warning: "/*" within comment [-Wcomment]
  142 | /**/
      |  
swap.cpp:27:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const ll INF = 1e18;
      |                ^~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:57:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (ll i = 0; i < weightInflate.size(); i++) weightShrink[weightInflate[i]] = i;
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 92 ms 13532 KB Output is correct
10 Correct 116 ms 16196 KB Output is correct
11 Correct 121 ms 15840 KB Output is correct
12 Correct 128 ms 16756 KB Output is correct
13 Correct 154 ms 16780 KB Output is correct
14 Correct 117 ms 13648 KB Output is correct
15 Correct 350 ms 22036 KB Output is correct
16 Correct 352 ms 21828 KB Output is correct
17 Correct 354 ms 22732 KB Output is correct
18 Execution timed out 2029 ms 22680 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2027 ms 18884 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 2 ms 600 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 3 ms 604 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 92 ms 13532 KB Output is correct
11 Correct 116 ms 16196 KB Output is correct
12 Correct 121 ms 15840 KB Output is correct
13 Correct 128 ms 16756 KB Output is correct
14 Correct 154 ms 16780 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 2 ms 600 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 2 ms 600 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 3 ms 604 KB Output is correct
34 Correct 13 ms 2648 KB Output is correct
35 Correct 138 ms 16400 KB Output is correct
36 Correct 128 ms 16496 KB Output is correct
37 Correct 122 ms 16448 KB Output is correct
38 Correct 119 ms 16408 KB Output is correct
39 Correct 117 ms 16324 KB Output is correct
40 Correct 111 ms 15232 KB Output is correct
41 Correct 149 ms 16928 KB Output is correct
42 Correct 129 ms 16456 KB Output is correct
43 Correct 176 ms 16384 KB Output is correct
44 Correct 128 ms 17224 KB Output is correct
45 Execution timed out 2045 ms 22724 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 92 ms 13532 KB Output is correct
10 Correct 116 ms 16196 KB Output is correct
11 Correct 121 ms 15840 KB Output is correct
12 Correct 128 ms 16756 KB Output is correct
13 Correct 154 ms 16780 KB Output is correct
14 Correct 117 ms 13648 KB Output is correct
15 Correct 350 ms 22036 KB Output is correct
16 Correct 352 ms 21828 KB Output is correct
17 Correct 354 ms 22732 KB Output is correct
18 Execution timed out 2029 ms 22680 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 92 ms 13532 KB Output is correct
11 Correct 116 ms 16196 KB Output is correct
12 Correct 121 ms 15840 KB Output is correct
13 Correct 128 ms 16756 KB Output is correct
14 Correct 154 ms 16780 KB Output is correct
15 Correct 117 ms 13648 KB Output is correct
16 Correct 350 ms 22036 KB Output is correct
17 Correct 352 ms 21828 KB Output is correct
18 Correct 354 ms 22732 KB Output is correct
19 Execution timed out 2029 ms 22680 KB Time limit exceeded
20 Halted 0 ms 0 KB -