Submission #1032263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032263		slivajan	Swapping Cities (APIO20_swap)	C++17	0 / 100	1 ms	344 KiB

swap

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

typedef long long un;
typedef vector<un> vuc;
typedef vector<bool> vol;

#define vec vector
#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)

constexpr un INF = 1e10;

constexpr un L = 20;

vuc otec;
vuc delka;
vuc chlup;

vuc hloubka;

vec<vuc> s_otec;
vec<vuc> s_delka;
vec<vuc> s_chlup;
vec<vuc> s_pred;

vec<vuc> synove;

vec<vuc> synmin;
vec<vuc> synkde;


un get_min_son(un i, un A = -1, un B = -1){

  vuc mins = synmin[i];
  vuc kdes = synkde[i];

  if (((kdes[0] == A) and (kdes[1] == B)) or ((kdes[0] == B) and (kdes[1] == A))){
    return mins[2];
  }

  if ((kdes[0] == A) or (kdes[0] == B)){
    return mins[1];
  }

  return mins[0];
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {

  vec<vec<pair<un, un>>> graph(N);

  REP(i, 0, M){
    graph[U[i]].push_back({V[i], W[i]});
    graph[V[i]].push_back({U[i], W[i]});
  }



  otec = vuc(N, -1);
  delka = vuc(N, INF);
  chlup = vuc(N, INF);

  priority_queue<tuple<un, un, un>> zasob;

  zasob.push({-INF, 0, -1});

  vol visited(N, false);

  while (not zasob.empty())
  {
    un now, w, dad;
    tie(w, now, dad) = zasob.top(); zasob.pop();

    if (visited[now]) continue;

    visited[now] = true;
    otec[now] = dad;
    delka[now] = -w;

    FEAC(psw, graph[now]){
      un son, weight;
      tie(son, weight) = psw;

      zasob.push({-weight, son, now});
    }

  }

  synove = vec<vuc>(N);

  
  synmin = vec<vuc>(N, vuc(3, INF));
  synkde = vec<vuc>(N, vuc(3, -1));

  REP(i, 0, N){
    FEAC(psw, graph[i]){
      un son, weight;
      tie(son, weight) = psw;

      if (son == otec[i]) continue;
      
      if (otec[son] == i) {
        synove[i].push_back(son);

        if (weight < synmin[i][0]){
          swap(synmin[i][1], synmin[i][2]);
          swap(synmin[i][0], synmin[i][1]);
          swap(synkde[i][1], synkde[i][2]);
          swap(synkde[i][0], synkde[i][1]);
          
          synmin[i][0] = weight;
          synkde[i][0] = son;
          
        }
        else if (weight < synmin[i][1]){
          swap(synmin[i][1], synmin[i][2]);
          swap(synkde[i][1], synkde[i][2]);
          
          synmin[i][1] = weight;
          synkde[i][1] = son;
        }
        else if (weight < synmin[i][2]){
          synmin[i][2] = weight;
          synkde[i][2] = son;
        }

      }
      else{
        chlup[i] = min(chlup[i], weight);
      }

    }
  }


  
  s_otec = vec<vuc>(L, vuc(N));
  s_delka = vec<vuc>(L, vuc(N));
  s_chlup = vec<vuc>(L, vuc(N));
  s_pred = vec<vuc>(L, vuc(N)); 
  
  s_otec[0] = otec;
  s_otec[0][0] = 0;

  s_delka[0] = delka;
  s_delka[0][0] = 0;

  s_chlup[0] = vuc(N, INF);

  iota(s_pred[0].begin(), s_pred[0].end(), 0);

  REP(l, 1, L){
    REP(i, 0, N){
      s_otec[l][i] = s_otec[l-1][s_otec[l-1][i]];
      s_delka[l][i] = max(s_delka[l-1][i], s_delka[l-1][s_otec[l-1][i]]);
      s_pred[l][i] = s_pred[l-1][s_otec[l-1][i]];
      s_chlup[l][i] = min({s_chlup[l-1][i], s_chlup[l-1][s_otec[l-1][i]],
                          get_min_son(s_otec[l-1][i], s_pred[l-1][i])});
    }
  }

  hloubka = vuc(N, 0);

  stack<pair<un, un>> zas;
  zas.push({0, 0});

  while (not zas.empty()){
    un now, depth;
    tie(now, depth) = zas.top(); zas.pop();

    hloubka[now] = depth;
    FEAC(s, synove[now]){
      zas.push({s, depth+1});
    }
  }
  
}

int getMinimumFuelCapacity(int X, int Y) {
  
  un chlup_ret = INF;
  un main_ret = 0;

  if (hloubka[X] > hloubka[Y]) swap(X, Y);


  if (hloubka[X] == 0){

    while (hloubka[Y] != 1)
    {
      un t = 0;

      while(hloubka[s_otec[t+1][Y]] >= 1) t++;

      main_ret = max(main_ret, s_delka[t][Y]);
      chlup_ret = min({chlup_ret, get_min_son(s_otec[t][Y], s_pred[t][Y]), s_chlup[t][Y]});
      Y = s_otec[t][Y];
    }

    main_ret = max(delka[Y], main_ret);

    return max(main_ret, chlup_ret);

  }
  
  while (hloubka[X] != hloubka[Y])
  {
    un t = 0;

    while(hloubka[s_otec[t+1][Y]] >= hloubka[X]) t++;

    main_ret = max(main_ret, s_delka[t][Y]);
    chlup_ret = min(chlup_ret, s_chlup[t][Y]);
    if (X != s_otec[t][Y]) chlup_ret = min({chlup_ret, get_min_son(s_otec[t][Y], s_pred[t][Y])});
    Y = s_otec[t][Y];
    
  }
  
  if (X == Y){
    return max(chlup_ret, main_ret);
  }

  while(otec[X] != otec[Y]){

    un t;
    while(s_otec[t+1][X] != s_otec[t+1][X]) t++;

    
    main_ret = max(main_ret, s_delka[t][Y]);
    chlup_ret = min({chlup_ret, get_min_son(s_otec[t][Y], s_pred[t][Y]), s_chlup[t][Y]});

    main_ret = max(main_ret, s_delka[t][X]);
    chlup_ret = min({chlup_ret, get_min_son(s_otec[t][X], s_pred[t][X]), s_chlup[t][X]});
    
    Y = s_otec[t][Y];
    X = s_otec[t][X];

  }

  main_ret = max({main_ret, delka[X], delka[Y]});
  chlup_ret = min({chlup_ret, get_min_son(otec[X], X, Y), delka[otec[X]]});
  return max(main_ret, chlup_ret);

}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:231:39: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  231 |     main_ret = max(main_ret, s_delka[t][Y]);
      |                                       ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27