Submission #314182

#TimeUsernameProblemLanguageResultExecution timeMemory
314182TAMREFSwapping Cities (APIO20_swap)C++17
0 / 100
196 ms28664 KiB
#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]);
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...