oj.uz

Submission #985688

# Submission time Handle Problem Language Result Execution time Memory
985688 2024-05-18T14:33:58 Z yoav_s Swapping Cities (APIO20_swap) C++17
17 / 100
 2000 ms 22024 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;

void init(int Nn, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    N = Nn;
    graph = vvp(N);
    for (ll i = 0; i < M; i++)
    {
      graph[U[i]].eb(V[i], W[i]);
      graph[V[i]].eb(U[i], W[i]);
      maxW = max(maxW, (ll)W[i]);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
  ll mini = 0, maxi = maxW + 1;
  while (mini < maxi)
  {
    ll mid = (mini + maxi) / 2;
    vv curGraph(N);
    for (ll i= 0 ; i < N; i++)
    {
      for (auto x : graph[i]) if (x.s <= mid) curGraph[i].pb(x.f);
    }
    v accessibleVertices;
    stack<ll> dfs;
    vb visited(N, false);
    dfs.push(X);
    while (!dfs.empty())
    {
      auto top = dfs.top();
      dfs.pop();
      if (visited[top]) continue;
      visited[top] = true;
      accessibleVertices.pb(top);
      for (ll x : curGraph[top]) dfs.push(x);
    }
    bool poss = false;
    if (visited[Y])
    {
      for (ll x : accessibleVertices) if (curGraph[x].size() >= 3) poss = true;
      ll edgeCount = 0;
      for (ll x : accessibleVertices) edgeCount += curGraph[x].size();
      edgeCount /= 2;
      if (edgeCount >= accessibleVertices.size()) poss = true;
    }
    if (poss)
    {
      maxi = mid;
    }
    else
    {
      mini = mid + 1;
    
    }
  }
  if (mini > maxW) return -1;
  return 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:131:1: warning: "/*" within comment [-Wcomment]
  131 | /**/
      |  
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 'int getMinimumFuelCapacity(int, int)':
swap.cpp:85:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |       if (edgeCount >= accessibleVertices.size()) poss = true;
      |           ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 9 ms 552 KB Output is correct
6 Correct 10 ms 348 KB Output is correct
7 Correct 11 ms 504 KB Output is correct
8 Correct 11 ms 568 KB Output is correct
9 Correct 386 ms 10792 KB Output is correct
10 Correct 937 ms 12932 KB Output is correct
11 Correct 1114 ms 12872 KB Output is correct
12 Correct 1415 ms 13712 KB Output is correct
13 Correct 1660 ms 13836 KB Output is correct
14 Execution timed out 2025 ms 12896 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2031 ms 16696 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 9 ms 552 KB Output is correct
6 Correct 10 ms 348 KB Output is correct
7 Correct 11 ms 504 KB Output is correct
8 Correct 11 ms 568 KB Output is correct
9 Correct 1 ms 500 KB Output is correct
10 Correct 9 ms 444 KB Output is correct
11 Correct 7 ms 344 KB Output is correct
12 Correct 8 ms 348 KB Output is correct
13 Correct 6 ms 536 KB Output is correct
14 Correct 10 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 7 ms 348 KB Output is correct
18 Correct 12 ms 348 KB Output is correct
19 Correct 8 ms 348 KB Output is correct
20 Correct 8 ms 568 KB Output is correct
21 Correct 7 ms 348 KB Output is correct
22 Correct 5 ms 540 KB Output is correct
23 Correct 10 ms 348 KB Output is correct
24 Correct 14 ms 596 KB Output is correct
25 Correct 15 ms 604 KB Output is correct
26 Correct 17 ms 604 KB Output is correct
27 Correct 6 ms 348 KB Output is correct
28 Correct 16 ms 348 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 9 ms 552 KB Output is correct
7 Correct 10 ms 348 KB Output is correct
8 Correct 11 ms 504 KB Output is correct
9 Correct 11 ms 568 KB Output is correct
10 Correct 386 ms 10792 KB Output is correct
11 Correct 937 ms 12932 KB Output is correct
12 Correct 1114 ms 12872 KB Output is correct
13 Correct 1415 ms 13712 KB Output is correct
14 Correct 1660 ms 13836 KB Output is correct
15 Correct 9 ms 444 KB Output is correct
16 Correct 7 ms 344 KB Output is correct
17 Correct 8 ms 348 KB Output is correct
18 Correct 6 ms 536 KB Output is correct
19 Correct 10 ms 344 KB Output is correct
20 Correct 11 ms 344 KB Output is correct
21 Correct 8 ms 344 KB Output is correct
22 Correct 7 ms 348 KB Output is correct
23 Correct 12 ms 348 KB Output is correct
24 Correct 8 ms 348 KB Output is correct
25 Correct 8 ms 568 KB Output is correct
26 Correct 7 ms 348 KB Output is correct
27 Correct 5 ms 540 KB Output is correct
28 Correct 10 ms 348 KB Output is correct
29 Correct 14 ms 596 KB Output is correct
30 Correct 15 ms 604 KB Output is correct
31 Correct 17 ms 604 KB Output is correct
32 Correct 6 ms 348 KB Output is correct
33 Correct 16 ms 348 KB Output is correct
34 Correct 44 ms 2460 KB Output is correct
35 Correct 799 ms 15336 KB Output is correct
36 Correct 773 ms 15296 KB Output is correct
37 Correct 789 ms 15212 KB Output is correct
38 Correct 875 ms 15216 KB Output is correct
39 Correct 797 ms 14860 KB Output is correct
40 Correct 857 ms 14072 KB Output is correct
41 Correct 1445 ms 15632 KB Output is correct
42 Correct 867 ms 15340 KB Output is correct
43 Correct 789 ms 15504 KB Output is correct
44 Correct 1468 ms 16108 KB Output is correct
45 Correct 1479 ms 18156 KB Output is correct
46 Correct 844 ms 15384 KB Output is correct
47 Correct 1106 ms 15260 KB Output is correct
48 Correct 992 ms 15800 KB Output is correct
49 Correct 114 ms 11756 KB Output is correct
50 Correct 206 ms 9040 KB Output is correct
51 Correct 1158 ms 13852 KB Output is correct
52 Correct 1827 ms 21080 KB Output is correct
53 Correct 1744 ms 22024 KB Output is correct
54 Execution timed out 2050 ms 21484 KB Time limit exceeded
55 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 9 ms 552 KB Output is correct
6 Correct 10 ms 348 KB Output is correct
7 Correct 11 ms 504 KB Output is correct
8 Correct 11 ms 568 KB Output is correct
9 Correct 386 ms 10792 KB Output is correct
10 Correct 937 ms 12932 KB Output is correct
11 Correct 1114 ms 12872 KB Output is correct
12 Correct 1415 ms 13712 KB Output is correct
13 Correct 1660 ms 13836 KB Output is correct
14 Execution timed out 2025 ms 12896 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 9 ms 552 KB Output is correct
7 Correct 10 ms 348 KB Output is correct
8 Correct 11 ms 504 KB Output is correct
9 Correct 11 ms 568 KB Output is correct
10 Correct 386 ms 10792 KB Output is correct
11 Correct 937 ms 12932 KB Output is correct
12 Correct 1114 ms 12872 KB Output is correct
13 Correct 1415 ms 13712 KB Output is correct
14 Correct 1660 ms 13836 KB Output is correct
15 Execution timed out 2025 ms 12896 KB Time limit exceeded
16 Halted 0 ms 0 KB -