#include <bits/stdc++.h> #include "incursion.h" #define respagold ios_base::sync_with_stdio(0), cin.tie(0); //#define int long long #define ll long long #define int2 __int128_t #define FOR( i, x, n, d ) for( int i = x; i <= n; i += d ) #define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d ) #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) (int)(x.size()) #define pb push_back #define ins insert #define lb lower_bound #define ub upper_bound #define pii pair <int, int> #define ppi pair <pair <int, int>, int> #define pip pair <int, pair <int, int>> #define mkp make_pair using namespace std; const int N = 1e6 + 12; const int inf = 1e18; const int mod = 1e9 + 7; const double eps = 1e-20; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; vector <int> g[N], t, siz, pa, used; int nn; mt19937 rng( chrono::steady_clock::now().time_since_epoch().count()); void dfs( int v, int p ) { pa[v] = p; for( auto to : g[v] ) { if( to != p ) { dfs(to, v); siz[v] += siz[to]; } } } int find_centroid( int v, int p = 0 ) { for( auto to : g[v] ) { if( to != p && siz[to] > nn / 2 ) return find_centroid(to, v); } return v; } vector <int> mark( vector <pair <int, int>> f, int s ) { set <int> st; for( auto i : f ) { g[i.F].pb(i.S); g[i.S].pb(i.F); st.ins(i.F), st.ins(i.S); } nn = sz(st); t = vector <int> (nn, 0); siz = vector <int> (nn + 1, 1); pa = vector <int> (nn + 1, 0); dfs(s, 0); int c2 = 0; int c = find_centroid(s, 0); for( auto v : g[c] ) { bool centroid_2 = 1; for( auto to : g[v] ) centroid_2 &= (siz[to] <= nn / 2); if( centroid_2 ) {c2 = v; break;} } dfs(c, c2); if(c2) dfs(c2, c); while(1) { t[s - 1] = 1; s = pa[s]; if( s == c || s == c2 ) { t[s - 1] = 1; break; } } for( auto v : st ) g[v].clear(); return t; } void locate( vector <pair <int, int>> f, int cur, int t ) { set <int> st; for( auto i : f ) { g[i.F].pb(i.S); g[i.S].pb(i.F); st.ins(i.F), st.ins(i.S); } nn = sz(st); int par = 0; siz = vector <int> (nn + 1, 1); pa = vector <int> (nn + 1, 0); dfs(cur, 0); int c2 = 0; int c = find_centroid(cur, 0); for( auto v : g[c] ) { bool centroid_2 = 1; for( auto to : g[v] ) centroid_2 &= (siz[to] <= nn / 2); if( centroid_2 ) {c2 = v; break;} } dfs(c, c2); used = vector <int> (nn + 1, 0); if(c2) dfs(c2, c); used[cur] = 1; while( t != 1 ) { t = visit(pa[cur]); cur = pa[cur]; used[cur] = 1; } siz = vector <int> (nn + 1, 1); dfs(cur, 0); while(1) { vector <pii> ord; for( auto to : g[cur] ) { if( to == pa[cur] || used[to] ) continue; ord.pb({siz[to], to}); } if( ord.empty() ) break; sort( all(ord) ); t = visit(ord[0].S); if( t == 1 ) { par = cur; cur = ord[0].S; continue; } if( sz(ord) > 1 ) { t = visit(cur); t = visit(ord[1].S); if( t == 1 ) { par = cur; cur = ord[1].S; continue; } } visit(cur); break; } return; }

incursion.cpp:26:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   26 | const int inf = 1e18;
      |                 ^~~~