Submission #314182

#	Time	Username	Problem	Language	Result	Execution time	Memory
314182		TAMREF	Swapping Cities (APIO20_swap)	C++17	0 / 100	196 ms	28664 KiB

swap

#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#include "swap.h"

const int mx = 1e5 + 5, lg = 17;
int n;
int d[mx], p[mx][lg], m[mx][lg], deg[mx];
int r[mx], w[mx], b[mx], z[mx], nl[mx];
int rt = -1;
vector<int> G[mx];

void init(int n){
    iota(r + 1, r + n + 1, 1);
    fill(z + 1, z + n + 1, 1);
    memset(b, 0x3f, sizeof(b));
    memset(nl, 0x3f, sizeof(nl));
    memset(m, 0x3f, sizeof(m));
}

int f(int x){
    return x == r[x] ? x : f(r[x]);
}

int c(int x, int y, int w_, int d_){
    debug("c(%d %d %d)\n",x,y,w_);
    x = f(x); y = f(y);
    if(z[x] < z[y]) swap(x, y);
    if(x != y){
        r[y] = x;
        w[y] = w_;
        if(nl[y] < 0x3f3f3f3f || !d_) nl[x] = min(nl[x], w_);
        if(!d_) b[y] = w_;
        z[x] += z[y];
        return 1;
    }else{
        nl[x] = min(nl[x], w_);
        return 0;
    }
}

void dfs(int x){
    ++d[x];
    p[x][0] = r[x];
    m[x][0] = b[x];
    for(int i = 1; (1 << i) <= d[x]; i++){
        p[x][i] = p[p[x][i-1]][i-1];
        m[x][i] = min(m[x][i-1], m[p[x][i-1]][i-1]);
    }
    for(int u : G[x]){
        d[u] = d[x];
        dfs(u);
    }
    //debug("dfs %d\n",x);
}

int lca(int i, int j){
    debug("qry %d %d\n",i,j);
    int answ = 0, ansb = INT_MAX;
    while(i != j){
        if(d[i] < d[j]) swap(i, j);
        answ = max(answ, w[i]);
        i = r[i];
    }
    for(int a = d[i], k = 0; a; a >>= 1, ++k){
        debug("climbing.. a = %d, i = %d\n",a,i);
        if(a & 1){
            ansb = min(ansb, m[i][k]);
            i = p[i][k];
        }
    }
    debug("answ = %d, ansb = %d\n",answ,ansb);
    return max(answ, ansb);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    vector<int> I(M); iota(all(I), 0);
    sort(all(I), [&](int u, int v){
        return W[u] < W[v];
    });
    init(n);
    for(int i : I){
        c(U[i] + 1, V[i] + 1, W[i], deg[U[i] + 1] <= 1 && deg[V[i] + 1] <= 1);
        ++deg[U[i] + 1];
        ++deg[V[i] + 1];
    }
    for(int i = 1; i <= n; i++){
        debug("r[%d] = %d\n",i,r[i]);
        if(i != r[i]){
            G[r[i]].pp(i);
        }else{
            rt = i;
        }
    }
    dfs(rt);
}

int getMinimumFuelCapacity(int X, int Y) {
    int v = lca(X + 1, Y + 1);
    return v < 0x3f3f3f3f ? v : -1;
}

#ifdef TAMREF
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;
}
#endif

Compilation message (stderr)

swap.cpp: In function 'int c(int, int, int, int)':
swap.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
swap.cpp:56:5: note: in expansion of macro 'debug'
   56 |     debug("c(%d %d %d)\n",x,y,w_);
      |     ^~~~~
swap.cpp: In function 'int lca(int, int)':
swap.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
swap.cpp:88:5: note: in expansion of macro 'debug'
   88 |     debug("qry %d %d\n",i,j);
      |     ^~~~~
swap.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
swap.cpp:96:9: note: in expansion of macro 'debug'
   96 |         debug("climbing.. a = %d, i = %d\n",a,i);
      |         ^~~~~
swap.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
swap.cpp:102:5: note: in expansion of macro 'debug'
  102 |     debug("answ = %d, ansb = %d\n",answ,ansb);
      |     ^~~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
swap.cpp:119:9: note: in expansion of macro 'debug'
  119 |         debug("r[%d] = %d\n",i,r[i]);
      |         ^~~~~

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