Submission #981406

#	Time	Username	Problem	Language	Result	Execution time	Memory
981406		Tsagana	Swapping Cities (APIO20_swap)	C++14	100 / 100	299 ms	44560 KiB

swap

#include "swap.h"

//OP
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define pi pair<int, int >
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mset multiset
#define F first
#define S second

using namespace std;

const int K = 23;

int  N;
int  M;
int  id;
int  fa[300001];
int  val[300001];
int  dep[300001];
int  back[300001];
int  G[300001][2];
int  front[300001];
int  sp[300001][K];
bool chain[300001];
vector<pair<int, pair<int, int>>> edges;

int find(int x) {return (x == fa[x] ? x : fa[x] = find(fa[x]));}

void dfs(int u, int f) {
  if (!u) return;
  dep[u] = dep[f] + 1; sp[u][0] = f;
  for (int i = 1; i < K; i++)  sp[u][i] = sp[sp[u][i-1]][i-1];
  for (int child = 0; child < 2; child++) dfs(G[u][child], u);
}

int lca(int u, int v) {
  if  (dep[v] >= dep[u]) swap(u, v);
  for (int i = K - 1; i >= 0; i--)
  if  (dep[sp[u][i]] >= dep[v]) u = sp[u][i];
  if  (u == v) return u;
  for (int i = K - 1; i >= 0; i--)
  if  (sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
  return sp[u][0];
}

void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
  N = _N; M = _M; id = N;
  for (int i = 0; i < M; i++) edges.pb({W[i], {U[i], V[i]}});
  sort(all(edges));
  for (int i = 0; i < 300001; i++) fa[i] = i;
  for (int i = 1; i <= N; i++) {chain[i] = 1; front[i] = back[i] = i;}
  for (int i = 0; i < M; i++) {
    int w = edges[i].F;
    int u = edges[i].S.F + 1;
    int v = edges[i].S.S + 1;
    int A = find(u);
    int B = find(v);

    if (A == B) {
      if (chain[A]) {
        int new_id = ++id; fa[A] = new_id;
        val[new_id] = w; G[new_id][0] = A;
      }
      continue;
    }
    int new_id = ++id;  fa[A] = new_id;  fa[B] = new_id;
    val[new_id] = w; G[new_id][0] = A; G[new_id][1] = B;
    if (chain[A] && chain[B]) {
      if (front[A] == v || back[A] == v) swap(A, B);
      if (front[A] == u) swap(front[A], back[A]);
      if (back[B]  == v) swap(front[B], back[B]);
      if (back[A]  == u && front[B] == v) {
        chain[new_id] = 1;
        front[new_id] = front[A];
        back[new_id]  = back[B];
      }
    }
  }
  dfs(id, 0);
}

int getMinimumFuelCapacity(int X, int Y) {
  X++; Y++; int l = lca(X, Y);
  if (!chain[l]) return val[l];
  for (int i = K - 1; i >= 0; i--)
    if (sp[l][i] && chain[sp[l][i]]) l = sp[l][i];
  return (l == id ? -1 : val[sp[l][0]]);
}
//ED

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