이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "swap.h"
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 2;
const int LOG = 18;
int n, m, cycle[MAXN], uf[MAXN], sz[MAXN], cnt[MAXN];
int dep[MAXN], bl[MAXN][LOG], bl_w[MAXN][LOG];
bool uf_bio[MAXN];
vector<int> nodes[MAXN];
vector<pair<int, int> > adj[MAXN], tree[MAXN];
vector<pair<int, pii> > edges;
int f(int x){
while(uf[x] != -1) x = uf[x];
return x;
}
void join(int u, int v, int edge){
if(uf_bio[u] ^ uf_bio[v]){
if(uf_bio[v]) swap(u, v);
for(int x : nodes[v]) cycle[x] = edge;
uf_bio[v] = 1;
}
if(sz[u] > sz[v]) swap(u, v);
sz[v] += sz[u];
uf[u] = v;
for(int x : nodes[u]) nodes[v].push_back(x);
}
int lift(int node, int step){
for(int i = 0; i < LOG; ++i){
if(step & 1 << i) node = bl[node][i];
}
return node;
}
int calc(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
int ret = 0, lift = u;
for(int i = 0; i < LOG; ++i){
if(dep[u] - dep[v] & 1 << i){
ret = max(ret, bl_w[lift][i]);
lift = bl[lift][i];
}
}
u = lift;
if(u == v) return ret;
for(int i = LOG - 1; i >= 0; --i){
if(bl[u][i] != bl[v][i]){
ret = max(ret, bl_w[u][i]);
ret = max(ret, bl_w[v][i]);
u = bl[u][i];
v = bl[v][i];
}
}
ret = max(ret, bl_w[u][0]);
ret = max(ret, bl_w[v][0]);
return ret;
}
void dfs(int node, int anc, int edge = 0){
bl[node][0] = anc;
bl_w[node][0] = edge;
dep[node] = dep[anc] + 1;
for(pii x : tree[node]){
if(x.X == anc) continue;
dfs(x.X, node, x.Y);
}
}
void connect(int node, int edge){
if(!uf_bio[node]){
uf_bio[node] = 1;
for(int x : nodes[node]) cycle[x] = edge;
}
}
void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w){
// n = _n; m = _m;
// for(int i = 0; i < n; ++i){
// uf[i] = -1; sz[i] = 1;
// nodes[i] = {i};
// }
//
// for(int i = 0; i < m; ++i){
// adj[u[i]].push_back({v[i], w[i]});
// adj[v[i]].push_back({u[i], w[i]});
// edges.push_back({w[i], {u[i], v[i]}});
// }
//
// sort(edges.begin(), edges.end());
//
// for(auto p : edges){
// int u = p.Y.X, v = p.Y.Y;
// ++cnt[u]; ++cnt[v];
// int fu = f(u), fv = f(v);
// if(cnt[u] >= 3) connect(fu, p.X);
// if(cnt[v] >= 3) connect(fv, p.X);
// u = fu; v = fv;
// if(u == v){
// connect(u, p.X);
// } else {
// join(u, v, p.X);
// tree[p.Y.X].push_back({p.Y.Y, p.X});
// tree[p.Y.Y].push_back({p.Y.X, p.X});
// }
// }
//
// dfs(0, 0);
//
// for(int j = 1; j < n; ++j){
// for(int i = 0; i < n; ++i){
// assert(bl[i][j - 1] >= 0);
// assert(bl[i][j - 1] < n);
// bl[i][j] = bl[bl[i][j - 1]][j - 1];
// bl_w[i][j] = max(bl_w[i][j - 1], bl_w[bl[i][j - 1]][j - 1]);
// }
// }
}
int getMinimumFuelCapacity(int x, int y){
if(x == y) return 0;
return -1;
if(m + 1 == n) return -1;
int val = calc(x, y);
return max(val, min(cycle[x], cycle[y]));
}
컴파일 시 표준 에러 (stderr) 메시지
swap.cpp: In function 'int calc(int, int)':
swap.cpp:42:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
42 | if(dep[u] - dep[v] & 1 << 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... |