///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///
#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
#define szz(s) int(s.size())
const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
int n, nn, m, q;
int p[N], b[N], check[N], nxt[25][N], h[N];
vector<int> adj[N];
struct edge{
int u, v, w;
} e[N];
bool cmp(edge a, edge b){
return a.w < b.w;
}
int Find(int u){
if(u == p[u]) return u;
return p[u] = Find(p[u]);
}
void Union(int u, int v){
++b[u]; ++b[v];
int uu = u, vv = v;
p[++n] = n;
u = Find(u); v = Find(v);
if(u == v){
p[u] = n;
adj[u].pb(n);
adj[n].pb(u);
check[n] = 1;
}else{
p[u] = n; p[v] = n;
check[n] = (check[u] || check[v] || b[uu] > 2 || b[vv] > 2);
adj[u].pb(n);
adj[n].pb(u);
adj[v].pb(n);
adj[n].pb(v);
}
}
void dfs(int u){
for(int v : adj[u]){
if(v == nxt[0][u]) continue;
h[v] = h[u] + 1;
nxt[0][v] = u;
dfs(v);
}
}
int lca(int u, int v){
if(h[u] < h[v]) swap(u, v);
REP(k, 20, 0){
int pu = nxt[k][u];
if(h[pu] >= h[v]){
u = pu;
}
}
if(u == v) return u;
REP(k, 20, 0){
int pu = nxt[k][u], pv = nxt[k][v];
if(pu != pv){
u = pu; v = pv;
}
}
return nxt[0][u];
}
int lift(int u, int mid){
REP(k, 20, 0){
if((1 << k) <= mid){
u = nxt[k][u];
mid -= (1 << k);
}
}
return u;
}
int getMinimumFuelCapacity(int u, int v){
int p = lca(u, v);
int l = 0, r = h[p];
while(l <= r){
int mid = (l + r) / 2;
if(check[lift(p, mid)]) r = mid - 1;
else l = mid + 1;
}
if(l > h[p]) return -1;
return e[lift(p, l) - nn].w;
}
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W){
nn = n;
FOR(i, 1, m){
e[i] = {U[i - 1], V[i - 1], W[i - 1]};
}
sort(e + 1, e + 1 + m, cmp);
FOR(u, 0, n) p[u] = u;
FOR(i, 1, m){
int u = e[i].u, v = e[i].v, w = e[i].w;
Union(u, v);
}
h[n] = 1;
dfs(n);
FOR(k, 1, 20){
FOR(u, 0, n){
nxt[k][u] = nxt[k - 1][nxt[k - 1][u]];
}
}
}
Compilation message
swap.cpp: In function 'void Union(int, int)':
swap.cpp:42:7: warning: operation on 'n' may be undefined [-Wsequence-point]
42 | p[++n] = n;
| ^~~
swap.cpp:42:7: warning: operation on 'n' may be undefined [-Wsequence-point]
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:119:37: warning: unused variable 'w' [-Wunused-variable]
119 | int u = e[i].u, v = e[i].v, w = e[i].w;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
25176 KB |
Output is correct |
| 2 |
Runtime error |
326 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
25176 KB |
Output is correct |
| 2 |
Runtime error |
326 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
25176 KB |
Output is correct |
| 2 |
Runtime error |
326 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
25176 KB |
Output is correct |
| 2 |
Runtime error |
326 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
25176 KB |
Output is correct |
| 2 |
Runtime error |
326 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
25176 KB |
Output is correct |
| 2 |
Runtime error |
326 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
