Submission #1032253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032253		Tonyl	Swapping Cities (APIO20_swap)	C++17	100 / 100	744 ms	80372 KiB

swap

#include "swap.h" //"grader.cpp"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
using ll = long long;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto &a : x)
#define all(x) (x).begin(), (x).end()
#define D(x) cerr << #x << ": " << x << endl;

int n, m;
vi weights;
vector<vector<pi>> w_to_edges;

struct History {
  int curr = -1;
  map<int, int> time_to_val;

  History() {
    time_to_val = {};
    update(0, 0);
  }

  History(int val) {
    time_to_val = {};
    update(0, val);
  }

  void update(int time, int val) {
    if (val == curr) return;
    time_to_val[time] = val;
    curr = val;
  }

  int at_time(int time) {
    auto iter = time_to_val.upper_bound(time);
    iter--;
    return (*iter).second;
  }
};


const int MAX_N = 100001;
int sz[MAX_N];
History parent[MAX_N], flag[MAX_N], neicount[MAX_N];

int root(int a) {
  if (parent[a].curr != a) return root(parent[a].curr);
  else return a;
}

int root_at(int tm, int a) {
  int par = parent[a].at_time(tm);
  if (par != a) return root_at(tm, par);
  else return a;
}

void join(int tm, int u, int v) {
  int a = root(u);
  int b = root(v);

  neicount[u].update(tm, neicount[u].curr+1);
  neicount[v].update(tm, neicount[v].curr+1);

  if (neicount[u].curr == 3 || neicount[v].curr == 3) flag[a].update(tm, 1);
  if (a == b) {
    flag[a].update(tm, 1); // cycle
    return;
  }

  if (sz[a] < sz[b]) swap(a,b);
  parent[b].update(tm, a);
  sz[a] += sz[b];
  if (flag[b].curr) flag[a].update(tm, 1);
}

bool were_good(int tm, int u, int v) {
  bool yay = false; //neicount[u].at_time(tm)>=2 || neicount[v].at_time(tm)>=2;
  u = root_at(tm, u); v = root_at(tm, v);
  yay = yay || flag[u].at_time(tm);
  return u == v && yay;
}

void go_insert() {
  REP(tm, weights.size()) {
    trav(e, w_to_edges[tm]) {
      join(tm+1, e.first, e.second);
    }
  }
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N; m = M;
  vector<pi> wp(m);
  REP(i,m) wp[i] = {W[i], i};
  sort(all(wp));
  int ind = -1, prev = -1;
  REP(i, m) {
    if (wp[i].first != prev) {
      prev = wp[i].first; ind++;
      weights.push_back(prev);
      w_to_edges.push_back(vector<pi>());
    }
    int j = wp[i].second;
    w_to_edges[ind].push_back({U[j], V[j]});
  }

  REP(i,n) parent[i] = History(i);
  REP(i,n) sz[i] = 1;

  go_insert();
}

int getMinimumFuelCapacity(int X, int Y) {

  int l = 0, r = weights.size()+1;
  while (l < r) {
    int mid = (l+r)/2;
    if (were_good(mid, X, Y)) {
      r = mid;
    } else {
      l = mid+1;
    }
  }

  assert(l==r);
  assert(l!=0);

  if (l > weights.size()) return -1;
  else return weights[l-1];
}

Compilation message (stderr)

swap.cpp: In function 'void go_insert()':
swap.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define REP(i,n) for (int i = 0; i < n; i++)
......
   86 |   REP(tm, weights.size()) {
      |       ~~~~~~~~~~~~~~~~~~            
swap.cpp:86:3: note: in expansion of macro 'REP'
   86 |   REP(tm, weights.size()) {
      |   ^~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:130:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   if (l > weights.size()) return -1;
      |       ~~^~~~~~~~~~~~~~~~

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