제출 #1262464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262464		mohammadsam	LOSTIKS (INOI20_lostiks)	C++20	100 / 100	1411 ms	387188 KiB

Main

/*
    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 && calc(s,E[i].sec) == 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(calc(s,t) == 0) ans = min(ans,dis[t]);
    if(ans == inf) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 36 / 36
• Subtask 3: 41 / 41