Submission #947109

#	Time	Username	Problem	Language	Result	Execution time	Memory
947109		Mohammadamin__Sh	LOSTIKS (INOI20_lostiks)	C++17	0 / 100	8 ms	29276 KiB

Main

//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
//#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 1e6 + 10 , maxm = 21 , MOD = 1e9 + 7;
const ll INF = 1e9 + 100;

int n , s , t , key[maxm] , door[maxm] , dp[(1<<maxm)][maxm] , mask[maxn] , par[maxn][maxm] , h[maxn] , path[maxm][maxm] , t_path[maxm] , ans = INF;
vector<pii> adj[maxn];

void Dfs(int v , int p){
    par[v][0] = p;
    for(int i = 1 ; i < maxm ; i++) par[v][i] = par[par[v][i-1]][i-1];
    for(pii u : adj[v]){
        if(u.F == p) continue;
        h[u.F] = h[v]+1;
        mask[u.F] = mask[v];
        if(u.S != -1){
            door[u.S] = v;
            mask[u.F] |= (1 << u.S);
        }
        Dfs(u.F , v);
    }
}

int Lca(int a , int b){
    if(h[a] < h[b]) swap(a , b);
    for(int i = 20 ; i >= 0 ; i--) if(h[par[a][i]] >= h[b]) a = par[a][i];
    if(a == b) return a;
    for(int i = 20 ; i >= 0 ; i--) if(par[a][i] != par[b][i]) a = par[a][i] , b = par[b][i];
    return par[a][0];
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);

    cin >> n >> s >> t;
    int cnt = 0;
    for(int i = 1 ; i < n ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        int tmp = -1;
        if(w != 0){
            tmp = cnt;
            key[cnt] = w;
            cnt++;
        }
        adj[u].pb({v , tmp});
        adj[v].pb({u , tmp});
    }
    h[0] = -1;
    Dfs(s , 0);
    for(int i = 0 ; i < cnt ; i++){
        for(int j = 0 ; j < cnt ; j++){
            if(i == j) continue;
            path[i][j] = h[door[i]] + 2*h[key[j]] + h[door[j]];
            int l1 = Lca(door[i] , key[j]) , l2 = Lca(door[j] , key[j]);
            path[i][j] -= (2*h[l1] + 2*h[l2]);
        }
    }
    for(int i = 0 ; i < cnt ; i++){
        int lca = Lca(t , door[i]) ;
        t_path[i] = h[door[i]] + h[t] - 2*h[lca];
    }
    for(int i = 0 ; i < cnt ; i++){
        if(!mask[door[i]] and !mask[key[i]]) dp[(1<<i)][i] = 2*h[key[i]]+h[door[i]];
        else dp[(1<<i)][i] = INF;
    }

    for(int i = 1 ; i < (1 << cnt); i++){
        for(int j = 0 ; j < cnt ; j++){
            if(__builtin_popcount(i) != 1) dp[i][j] = INF;
            if((i & (1 << j)) == 0) continue;
            int x = i ^ (1 << j);
            if((mask[door[j]] & x) != mask[door[j]]) continue;
            if((mask[key[j]] & x) != mask[key[j]]) continue;
            for(int k = 0 ; k < cnt ; k++){
                if(dp[x][k] == INF or k == j) continue;
                dp[i][j] = min(dp[i][j] , dp[x][k] + path[k][j]);
            }
            if((mask[t] & i) == mask[t]) ans = min(dp[i][j] + t_path[j] , ans);
        }
    }
    if(ans == INF) ans = -1;
    cout << ans << '\n';
}

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