#include "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ll long long
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+10 + 10, inf = 1e9+10 , mod = 1e9 + 7 , lg = 20 ;
int cnt = 1 , par[maxn] , dis[maxn] , mark[maxn] , p[maxn][lg+1] , mn[maxn][lg+1] , mn2[maxn][lg+1] ;
vector <pii> T[maxn] ;
vector <pii> G[maxn];
set <pii> s[maxn] ;
int find(int v){
if(par[v]==0)return v;
return par[v] = find(par[v]) ;
}
vector<int> tp;
void dfs(int v, int r =0){
p[v][0] = r ;
mark[v] =1 ;
tp.pb(v);
for(auto [w,u] : T[v]){
if(r == u)continue ;
dis[u] = dis[v] + 1;
mn2[u][0] = w;
cout << u << " " << w << "\n" ;
dfs(u , v) ;
if(sz(s[u]) > sz(s[v]))swap(s[v],s[u]);
while(sz(s[u])){
s[v].insert(*s[u].begin());
s[u].erase(s[u].begin());
}
}
for(auto [w,u] : G[v]){
if(dis[u] < dis[v]){
s[v].insert({w,u}) ;
}
}
mn[v][0] = inf ;
while(sz(s[v])){
int u =(*s[v].begin()).S , w = (*s[v].begin()).F ;
if(dis[v]<=dis[u]){
s[v].erase(s[v].begin());
continue ;
}
mn[v][0] = w ;
break ;
}
}
pii up(int v ,int d){
int r = inf , r2 = 0;
rep(i , 0 ,lg)if(d>>i&1){
r = min(r , mn[v][i]) ;
r2= max(r2 , mn2[v][i]) ;
v = p[v][i] ;
}
return (pii){r,r2};
}
int up2(int v ,int d){
rep(i , 0 ,lg)if(d>>i&1){
v = p[v][i] ;
}
return v;
}
int lca(int v, int u){
if(dis[v] < dis[u])swap(v,u);
pii a = up(v , dis[v]-dis[u]) ;
v = up2(v,dis[v]-dis[u]) ;
int a1 = a.F ,a2 =a.S;
per(i , lg , 0){
if(p[v][i] != p[u][i]){
a1 = min({a1 ,mn[v][i] , mn[u][i]});
a2 = max({a2 ,mn2[v][i] , mn2[u][i]}) ;
v = p[v][i] ;
u = p[u][i] ;
}
}
if(v==u)return max(a1 ,a2) ;
a1 = min({a1 ,mn[v][0] , mn[u][0]});
a2 = max({a2 ,mn2[v][0] , mn2[u][0]}) ;
return max(a1 ,a2);
}
void init(int n, int m,vector<int>U, vector<int> V, vector<int> W) {
vector<pair<int,pii> > ed;
rep(i , 0 , m-1){
V[i]++;U[i]++;
ed.pb({W[i] , {V[i],U[i]}});
}
sort(all(ed));
rep(i , 0 ,sz(ed)-1){
int v = ed[i].S.F, u = ed[i].S.S , w = ed[i].F ;
if(find(v) == find(u)){
G[v].pb({w,u});
G[u].pb({w,v}) ;
}else{
par[find(v)] = find(u);
T[v].pb({w,u});
T[u].pb({w,v});
}
}
rep(i ,1 , n){
if(mark[i] == 1)continue ;
dfs(i) ;
}
for(int v : tp){
rep(i , 1 ,lg){
p[v][i] = p[p[v][i-1]][i-1];
mn[v][i] = min(mn[v][i-1] , mn[p[v][i-1]][i-1]) ;
mn2[v][i] = max(mn2[v][i-1] , mn2[p[v][i-1]][i-1]) ;
}
}
}
int getMinimumFuelCapacity(int v, int u) {
v++ ;u++;
if(find(v)!=find(u))return -1 ;
int ans = lca(v,u);
if(ans == inf)return -1 ;
return ans;
}
/* g++ -Wall -lm -static -DEVAL -o swap -O2 swap.cpp grader.cpp -std=c++17 */
Compilation message
swap.cpp: In function 'void dfs(int, int)':
swap.cpp:34:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | for(auto [w,u] : T[v]){
| ^
swap.cpp:46:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
46 | for(auto [w,u] : G[v]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
