#include <bits/stdc++.h>
#include <swap.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 2e5 + 5, lg = 20, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
struct Edge{
int u, v, w;
bool operator<(Edge a){
return w < a.w;
}
};
int ext_path[maxn], par[maxn], br[maxn][2];
vector<int> grp[maxn];
vector<pp> adj[maxn];
int get(int x){
return par[x] == -1? x: par[x] = get(par[x]);
}
bool unite(int u, int v, int w){
int a = u, b = v;
u = get(u), v = get(v);
if(u == v){
if(ext_path[u] == -1){
for(int c: grp[u]) ext_path[c] = w;
}
return false;
}
if(sz(grp[u]) < sz(grp[v])) swap(u, v);
par[v] = u;
if(ext_path[u] + 1){
if(ext_path[v] == -1) for(int c: grp[v]) ext_path[c] = w;
}else{
if(ext_path[v] + 1) for(int c: grp[u]) ext_path[c] = w;
else{
int t1 = -1, t2 = -1;
rep(i,0,2) if(br[u][i] == a) t1 = i;
rep(i,0,2) if(br[v][i] == b) t2 = i;
if(t1 == -1 || t2 == -1){
for(int c: grp[u]) ext_path[c] = w;
for(int c: grp[v]) ext_path[c] = w;
}else{
br[u][t1] = br[v][t2^1];
}
}
}
for(int c: grp[v]) grp[u].pb(c); grp[v].clear();
return true;
}
pp rmq[maxn][lg];
int h[maxn];
void dfs(int r, int p){
rep(i,1,lg){
rmq[r][i].ff = rmq[rmq[r][i-1].ff][i-1].ff;
rmq[r][i].ss = max(rmq[r][i-1].ss, rmq[rmq[r][i-1].ff][i-1].ss);
}
for(auto[c, w]: adj[r]) if(c - p){
h[c] = h[r] + 1, rmq[c][0] = {r, w};
dfs(c, r);
}
}
int lca(int u, int v){
if(h[u] > h[v]) swap(u, v);
per(i,lg-1,0) if(h[rmq[v][i].ff] >= h[u]) v = rmq[v][i].ff;
if(u == v) return u;
per(i,lg-1,0) if(rmq[u][i].ff - rmq[v][i].ff) v = rmq[v][i].ff, u = rmq[u][i].ff;
return rmq[u][0].ff;
}
int query(int u, int l){
int ans = 0;
per(i,lg-1,0) if(h[rmq[u][i].ff] >= h[l]) ans = max(ans, rmq[u][i].ss), u = rmq[u][i].ff;
return ans;
}
int mx = -1;
int getMinimumFuelCapacity(int u, int v){
if(ext_path[u] == -1) return -1;
return mx;
int l = lca(u, v);
return max({query(u, l), query(v, l), ext_path[u]});
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
vector<Edge> edg;
vector<int> cnt(n);
rep(i,0,m){
// int u, v, w; cin >> u >> v >> w;
edg.pb({u[i], v[i], w[i]});
mx = max(mx, w[i]), cnt[u[i]]++, cnt[v[i]]++;
} sort(all(edg));
rep(i,0,n) assert(cnt[i] < 3);
rep(i,0,n) par[i] = ext_path[i] = -1, br[i][0] = br[i][1] = i, grp[i].pb(i);
for(auto[u, v, w]: edg){
if(unite(u, v, w)) {
adj[u].pb({v, w}), adj[v].pb({u, w});
}
} dfs(0, 0);
// int q; cin >> q;
// while(q--){
// int u, v; cin >> u >> v;
// cout << getMinimumFuelCapacity(u, v) << '\n';
// }
}
// int main(){
// cin.tie(0) -> sync_with_stdio(0);
// int n, m; cin >> n >> m;
// vector<Edge> edg;
// rep(i,0,m){
// int u, v, w; cin >> u >> v >> w;
// edg.pb({u, v, w});
// } sort(all(edg));
// rep(i,0,n) par[i] = ext_path[i] = -1, br[i][0] = br[i][1] = i, grp[i].pb(i);
// for(auto[u, v, w]: edg){
// if(unite(u, v, w)) {
// er(u, v, w);
// adj[u].pb({v, w}), adj[v].pb({u, w});
// }
// } dfs(0, 0);
// rep(i,0,n) er(i, ext_path[i]);
// int q; cin >> q;
// while(q--){
// int u, v; cin >> u >> v;
// cout << getMinimumFuelCapacity(u, v) << '\n';
// }
// return 0;
// }
Compilation message
swap.cpp: In function 'bool unite(int, int, int)':
swap.cpp:63:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
63 | for(int c: grp[v]) grp[u].pb(c); grp[v].clear();
| ^~~
swap.cpp:63:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
63 | for(int c: grp[v]) grp[u].pb(c); grp[v].clear();
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Runtime error |
84 ms |
30272 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
