oj.uz

Submission #314182

# Submission time Handle Problem Language Result Execution time Memory
314182 2020-10-19T00:49:02 Z TAMREF Swapping Cities (APIO20_swap) C++17
0 / 100
 196 ms 28664 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10112 KB Output is correct
2 Correct 6 ms 10112 KB Output is correct
3 Correct 6 ms 10112 KB Output is correct
4 Correct 7 ms 10240 KB Output is correct
5 Correct 7 ms 10240 KB Output is correct
6 Correct 7 ms 10240 KB Output is correct
7 Correct 7 ms 10240 KB Output is correct
8 Correct 7 ms 10240 KB Output is correct
9 Correct 78 ms 21756 KB Output is correct
10 Correct 95 ms 24188 KB Output is correct
11 Correct 95 ms 23932 KB Output is correct
12 Correct 99 ms 24824 KB Output is correct
13 Correct 79 ms 24180 KB Output is correct
14 Correct 86 ms 22008 KB Output is correct
15 Correct 192 ms 28152 KB Output is correct
16 Correct 190 ms 27768 KB Output is correct
17 Correct 196 ms 28664 KB Output is correct
18 Correct 167 ms 28060 KB Output is correct
19 Incorrect 92 ms 16504 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10112 KB Output is correct
2 Correct 6 ms 10112 KB Output is correct
3 Incorrect 146 ms 26864 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 10112 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 10112 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10112 KB Output is correct
2 Correct 6 ms 10112 KB Output is correct
3 Correct 6 ms 10112 KB Output is correct
4 Correct 7 ms 10240 KB Output is correct
5 Correct 7 ms 10240 KB Output is correct
6 Correct 7 ms 10240 KB Output is correct
7 Correct 7 ms 10240 KB Output is correct
8 Correct 7 ms 10240 KB Output is correct
9 Correct 78 ms 21756 KB Output is correct
10 Correct 95 ms 24188 KB Output is correct
11 Correct 95 ms 23932 KB Output is correct
12 Correct 99 ms 24824 KB Output is correct
13 Correct 79 ms 24180 KB Output is correct
14 Correct 86 ms 22008 KB Output is correct
15 Correct 192 ms 28152 KB Output is correct
16 Correct 190 ms 27768 KB Output is correct
17 Correct 196 ms 28664 KB Output is correct
18 Correct 167 ms 28060 KB Output is correct
19 Incorrect 146 ms 26864 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 10112 KB Output isn't correct