oj.uz

Submission #985693

# Submission time Handle Problem Language Result Execution time Memory
985693 2024-05-18T14:36:23 Z yoav_s Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 16852 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;
    v Ws;
    for (auto x : W) Ws.pb(x);
    sort(all(Ws));
    Ws.erase(unique(all(Ws)), Ws.end());
    map<ll, ll> weightShrink;
    for (ll i = 0; i < Ws.size(); i++) weightShrink[Ws[i]] = i;
    maxW = Ws.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 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 < Ws.size(); i++) weightShrink[Ws[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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 568 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 248 ms 10808 KB Output is correct
10 Correct 529 ms 13072 KB Output is correct
11 Correct 640 ms 12768 KB Output is correct
12 Correct 708 ms 13708 KB Output is correct
13 Correct 834 ms 13444 KB Output is correct
14 Execution timed out 2077 ms 10976 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Execution timed out 2033 ms 16852 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 568 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 568 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 248 ms 10808 KB Output is correct
10 Correct 529 ms 13072 KB Output is correct
11 Correct 640 ms 12768 KB Output is correct
12 Correct 708 ms 13708 KB Output is correct
13 Correct 834 ms 13444 KB Output is correct
14 Execution timed out 2077 ms 10976 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -