#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define int long long
template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }
const int N = 3e5+5;
const int mod = 1e9+7;
int n, m, par[N], d[N], f[N], w[N];
vector<int> edges[N];
int lca[N][30], tin[N], tout[N], t;
int fx(int x) { return (x == par[x] ? x : par[x] = fx(par[x])); }
void merge(int a, int b, int c){
d[a]++, d[b]++;
int cnd = (max(d[a], d[b]) >= 3);
a = fx(a), b = fx(b);
edges[n].pb(a), edges[n].pb(b);
if(a == b){
par[a] = par[b] = n;
par[n] = n, f[n] = 1, w[n] = c;
} else {
par[a] = par[b] = n, w[n] = c;
par[n] = n, f[n] = f[a] | f[b] | cnd;
} n++;
}
void dfs(int u, int p){
tin[u] = t++;
lca[u][0] = p;
for(int j=1;j<30;j++) lca[u][j] = lca[lca[u][j-1]][j-1];
for(auto x : edges[u]) dfs(x, u);
tout[u] = t - 1;
}
void init(int32_t N, int32_t M,
vector<int32_t> a, vector<int32_t> b, vector<int32_t> c) {
n = N, m = M;
vector<array<int, 3>> tt;
for(int i=0;i<m;i++) tt.pb({c[i], a[i], b[i]});
sort(tt.begin(), tt.end());
for(int i=0;i<n;i++) par[i] = i;
for(auto x : tt) merge(x[1], x[2], x[0]);
memset(lca, -1, sizeof lca);
dfs(n-1, n-1);
}
bool up(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }
int f_lca(int a, int b){
if(up(b, a)) return b;
if(up(a, b)) return a;
for(int i=29;i>=0;i--){
if(up(lca[a][i], b)) continue;
a = lca[a][i];
} return lca[a][0];
}
int32_t getMinimumFuelCapacity(int32_t x, int32_t y) {
int lc = f_lca(x, y);
if(f[lc]) return w[lc];
for(int i=29;i>=0;i--){
if(f[lca[lc][i]]) continue;
lc = lca[lc][i];
} return w[lca[lc][0]];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
37 ms |
77804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
37 ms |
77804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
37 ms |
77804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
37 ms |
77804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
37 ms |
77804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
37 ms |
77804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |