oj.uz

Submission #985706

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

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]]);
    }
}

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 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:137:1: warning: "/*" within comment [-Wcomment]
  137 | /**/
      |  
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:51:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (ll i = 0; i < weightInflate.size(); i++) weightShrink[weightInflate[i]] = i;
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:91:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |       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 1 ms 500 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 267 ms 11048 KB Output is correct
10 Correct 729 ms 13404 KB Output is correct
11 Correct 825 ms 13224 KB Output is correct
12 Correct 709 ms 13880 KB Output is correct
13 Correct 857 ms 13864 KB Output is correct
14 Execution timed out 2037 ms 11468 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 2050 ms 17024 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 1 ms 500 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 4 ms 580 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 4 ms 348 KB Output is correct
16 Correct 4 ms 568 KB Output is correct
17 Correct 6 ms 348 KB Output is correct
18 Correct 5 ms 496 KB Output is correct
19 Correct 5 ms 560 KB Output is correct
20 Correct 4 ms 348 KB Output is correct
21 Correct 4 ms 348 KB Output is correct
22 Correct 4 ms 604 KB Output is correct
23 Correct 5 ms 348 KB Output is correct
24 Correct 7 ms 604 KB Output is correct
25 Correct 7 ms 600 KB Output is correct
26 Correct 6 ms 604 KB Output is correct
27 Correct 4 ms 560 KB Output is correct
28 Correct 7 ms 604 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 267 ms 11048 KB Output is correct
11 Correct 729 ms 13404 KB Output is correct
12 Correct 825 ms 13224 KB Output is correct
13 Correct 709 ms 13880 KB Output is correct
14 Correct 857 ms 13864 KB Output is correct
15 Correct 4 ms 580 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 4 ms 344 KB Output is correct
18 Correct 4 ms 348 KB Output is correct
19 Correct 4 ms 348 KB Output is correct
20 Correct 4 ms 348 KB Output is correct
21 Correct 4 ms 568 KB Output is correct
22 Correct 6 ms 348 KB Output is correct
23 Correct 5 ms 496 KB Output is correct
24 Correct 5 ms 560 KB Output is correct
25 Correct 4 ms 348 KB Output is correct
26 Correct 4 ms 348 KB Output is correct
27 Correct 4 ms 604 KB Output is correct
28 Correct 5 ms 348 KB Output is correct
29 Correct 7 ms 604 KB Output is correct
30 Correct 7 ms 600 KB Output is correct
31 Correct 6 ms 604 KB Output is correct
32 Correct 4 ms 560 KB Output is correct
33 Correct 7 ms 604 KB Output is correct
34 Correct 25 ms 2152 KB Output is correct
35 Correct 717 ms 13768 KB Output is correct
36 Correct 751 ms 14100 KB Output is correct
37 Correct 787 ms 14000 KB Output is correct
38 Correct 855 ms 13724 KB Output is correct
39 Correct 777 ms 13556 KB Output is correct
40 Correct 798 ms 13064 KB Output is correct
41 Correct 760 ms 13992 KB Output is correct
42 Correct 724 ms 13892 KB Output is correct
43 Correct 727 ms 13888 KB Output is correct
44 Correct 1002 ms 14308 KB Output is correct
45 Correct 1181 ms 17920 KB Output is correct
46 Correct 758 ms 14008 KB Output is correct
47 Correct 930 ms 13804 KB Output is correct
48 Correct 872 ms 14368 KB Output is correct
49 Correct 183 ms 17092 KB Output is correct
50 Correct 208 ms 12744 KB Output is correct
51 Correct 702 ms 15320 KB Output is correct
52 Correct 1209 ms 20508 KB Output is correct
53 Correct 1113 ms 22156 KB Output is correct
54 Correct 1531 ms 23648 KB Output is correct
55 Correct 764 ms 15692 KB Output is correct
56 Correct 1435 ms 25244 KB Output is correct

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 1 ms 500 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 267 ms 11048 KB Output is correct
10 Correct 729 ms 13404 KB Output is correct
11 Correct 825 ms 13224 KB Output is correct
12 Correct 709 ms 13880 KB Output is correct
13 Correct 857 ms 13864 KB Output is correct
14 Execution timed out 2037 ms 11468 KB Time limit exceeded
15 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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 267 ms 11048 KB Output is correct
11 Correct 729 ms 13404 KB Output is correct
12 Correct 825 ms 13224 KB Output is correct
13 Correct 709 ms 13880 KB Output is correct
14 Correct 857 ms 13864 KB Output is correct
15 Execution timed out 2037 ms 11468 KB Time limit exceeded
16 Halted 0 ms 0 KB -