Submission #1262459

#TimeUsernameProblemLanguageResultExecution timeMemory
1262459mohammadsamLOSTIKS (INOI20_lostiks)C++20
36 / 100
1012 ms204544 KiB
/* in the name of god */ //#pragma GCC optimize("Ofast,O3,unroll-loops") //#pragma GCC target("avx,avx2,fma") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native") #include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int> pii; typedef pair<long long ,long long> pll; typedef long long ll ; #define File freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define all(V) V.begin(),V.end() #define setprec(x) fixed << setprecision(x) #define Mp(a,b) make_pair(a,b) #define len(V) (int)(V.size()) #define sep ' ' #define endl '\n' #define pb push_back #define fi first #define sec second #define popcount(x) __builtin_popcount(x) #define lid u<<1 #define rid (lid)|1 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 1e6 + 10,M=22,SQ=320,LOG=21; const ll inf = 1e16 , MD = 1e9 + 7; inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);} int n , m; vector<pii> g[N]; vector<pair<pii,int>> E; int s,t; int par[N][LOG]; int ps[N]; int dis[N]; int F[M][M]; int D[M][M]; int dp[1<<21][M]; void dfs(int u,int p){ par[u][0] = p; dis[u] = (u == p ? 0 : dis[p] + 1); for(int j=1 ; j < LOG;j++) par[u][j] = par[par[u][j-1]][j-1]; for(auto h : g[u]){ if(h.fi != p){ ps[h.fi] = ps[u] ^ h.sec; dfs(h.fi,u); } } } int lift(int u,int k){ for(int j = 0 ; j < LOG;j++) if(k&(1<<j)) u = par[u][j]; return u; } int lca(int u,int v){ if(dis[u] > dis[v]) swap(u,v); v = lift(v,dis[v] - dis[u]); if(u==v) return u; for(int j =LOG-1;j >= 0;j--) if(par[u][j]^par[v][j]) u = par[u][j],v=par[v][j]; return par[u][0]; } int DIS(int u,int v){ return dis[u] + dis[v] - 2*dis[lca(u,v)]; } int calc(int u,int v){ return (ps[u] ^ ps[v]); } int32_t main() { ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0); cin >> n ; cin >> s >> t; for(int i = 0 ; i < n - 1;i++){ int u,v,w; cin >> u >> v >> w; int w2 = (w == 0 ? 0 : (1<<m)); if(w) m++; g[u].pb({v,w2}); g[v].pb({u,w2}); if(w) E.pb({{u,v},w}); } dfs(s,s); for(int i = 0;i < m;i++){ if(par[E[i].fi.sec][0] != E[i].fi.fi) swap(E[i].fi.sec,E[i].fi.fi); } for(int i = 0 ; i < m;i++){ for(int j = 0; j < m;j++){ F[i][j] = calc(E[i].sec,E[j].fi.fi); D[i][j] = DIS(E[i].sec,E[j].fi.fi); } } for(int mask = 0;mask < (1<<m);mask++){ for(int i = 0; i < m;i++) dp[mask][i] = inf; } for(int i = 0; i < m ;i++){ if(F[i][i] == 0) dp[1<<i][i] = dis[E[i].sec] + D[i][i]; } for(int mask = 0;mask < (1<<m);mask++){ if(popcount(mask) <= 1) continue; for(int i = 0; i < m ;i++){ if(mask&(1<<i)){ int nmask = mask^(1<<i); for(int j = 0 ; j < m;j++){ if(mask&(1<<j) && j != i){ int tmp = D[i][j] + D[i][i] + dp[nmask][j]; if(((F[i][j]&nmask) == F[i][j]) && ((F[i][i]&nmask) == F[i][i])) dp[mask][i] = min(dp[mask][i],tmp); } } } } } int ans = inf; for(int mask = 0;mask < (1<<m);mask++){ for(int i = 0; i < m;i++){ if(mask&(1<<i)){ if((calc(E[i].fi.fi,t)&mask) == calc(E[i].fi.fi,t)) ans = min(ans,dp[mask][i] + DIS(t,E[i].fi.fi)); } } } if(ans == inf) cout << -1 << endl; else cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...