이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
컴파일 시 표준 에러 (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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |