Submission #741408

#	Time	Username	Problem	Language	Result	Execution time	Memory
741408		vjudge1	Swapping Cities (APIO20_swap)	C++17	Compilation error	0 ms	0 KiB

swap

#include "swap.h"

#include <cassert>
#include <cstdio>

#include <string>
#include <vector>

/////////////////////////////////////////////////////

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

template<typename T> int SIZE(T (&t)){ return t.size(); } template<typename T, size_t N> int SIZE(T (&t)[N]){ return N; } string to_string(char t){ return "'" + string({t}) + "'"; } string to_string(bool t){ return t ? "true" : "false"; } string to_string(const string &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += t[i]; } return '"' + ret + '"'; } string to_string(const char* t){ string ret(t); return to_string(ret); } template<size_t N> string to_string(const bitset<N> &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){ ret += t[i] + '0'; } return to_string(ret); } template<typename T, typename... Coords> string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C); template<typename T, typename S> string to_string(const pair<T, S> &t){ return "(" + to_string(t.first) + ", " + to_string(t.second) + ")"; } template<typename T, typename... Coords> string to_string(const T (&t), int x1, int x2, Coords... C){ string ret = "["; x1 = min(x1, SIZE(t)); auto e = begin(t); advance(e,x1); for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += to_string(*e, C...) + (i != _i ? ", " : ""); e = next(e); } return ret + "]"; } template<int Index, typename... Ts> struct print_tuple{ string operator() (const tuple<Ts...>& t) { string ret = print_tuple<Index - 1, Ts...>{}(t); ret += (Index ? ", " : ""); return ret + to_string(get<Index>(t)); } }; template<typename... Ts> struct print_tuple<0, Ts...> { string operator() (const tuple<Ts...>& t) { return to_string(get<0>(t)); } }; template<typename... Ts> string to_string(const tuple<Ts...>& t) { const auto Size = tuple_size<tuple<Ts...>>::value; return print_tuple<Size - 1, Ts...>{}(t); } void dbgr(){;} template<typename Heads, typename... Tails> void dbgr(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgr(T...); } void dbgs(){;} template<typename Heads, typename... Tails> void dbgs(Heads H, Tails... T){ cout << H << " "; dbgs(T...); } 
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int MAXA = 1e9 + 7;
int n, m;
array<int, 3> edge[M];
vector <int> a[N];
int ma = 0;
bool vis[N];

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N; m = M;
  for(int i = 0; i < m; ++i){
    edge[i] = {U[i], V[i], W[i]};
    ma = max(ma, W[i]);
    //a[U[i]].push_back({V[i], W[i]});
    //a[V[i]].push_back({U[i], W[i]});
  }
}

void bfs(vector <int> &d, int u, int ban = -1){
  queue<int> q;
  q.push(u);
  while (!q.empty()){
    int u = q.front(); q.pop();
    for(int i : a[u]){
      if (i == ban) continue;
      if (d[i] == MAXA){
        d[i] = d[u] + 1;
        q.push(i);
      }
    }
  }
}

bool f(int mid, int X, int Y){
  for(int i = 0; i < n; ++i) a[i].clear();
  for(int i = 0; i < m; ++i){
    if (edge[i][2] <= mid) {
      a[edge[i][0]].push_back(edge[i][1]);
      a[edge[i][1]].push_back(edge[i][0]);
    }
  }

  vector <int> d(n, MAXA);
  d[X] = 0; bfs(d, X);

  vector <int> dx(n, MAXA), dy(n, MAXA);
  dx[X] = 0; bfs(dx, X, Y);
  dy[Y] = 0; bfs(dy, Y, X);

  //dbg(dx, 0, n - 1);
  //dbg(dy, 0, n - 1);

  int disxy = d[Y];
  if (disxy >= MAXA) return false; 

  int ct = 0;
  for(int i = 0; i < n; ++i){
    if (dx[i] == MAXA || dy[i] == MAXA) continue;
    ++ct;
  }

  return (ct > disxy - 1);
}

int getMinimumFuelCapacity(int X, int Y) {
  int l = 0, r = MAXA;
  while (l + 1 < r){
    int mid = (l + r) >> 1;
    if (f(mid, X, Y)) r = mid;
    else l = mid;
  }
  if (r == MAXA) r = -1;

  return r;
}

///////////////////////////////////////////////////////

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 (stderr)

/usr/bin/ld: /tmp/ccTMVxFd.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cconQuzg.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status