Submission #1265607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265607		Hamed_Ghaffari	LOSTIKS (INOI20_lostiks)	C++20	100 / 100	939 ms	405848 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define mins(a, b) (a = min(a, b))

const int MXN = 1e6+5, MXM = 21, inf = 1e9;

int n, s, t, U[MXN], V[MXN], W[MXN], key[MXM], door[MXM], par[MXM][MXN], h[MXN], dis[MXM][MXM];
int mask[MXN], dp[MXM][1<<MXM], timer, dest[MXM];
vector<int> g[MXN];

void dfs(int v) {
    for(int i=1; i<MXM; i++) par[i][v] = par[i-1][par[i-1][v]];
    for(int i : g[v]) {
        int u = v^U[i]^V[i];
        if(u==par[0][v]) continue;
        par[0][u] = v;
        h[u] = h[v]+1;
        mask[u] = mask[v];
        if(W[i]!=-1) {
            door[W[i]] = v;
            mask[u] |= 1<<W[i];
        } 
        dfs(u);
    }
}
inline int jump(int v, int d) {
    for(int i=0; i<MXM; i++)
        if(d>>i&1)
            v = par[i][v];
    return v;
}
inline int LCA(int u, int v) {
    if(h[u]<h[v]) swap(u, v);
    u = jump(u, h[u]-h[v]);
    if(u==v) return u;
    for(int i=MXM-1; i>=0; i--)
        if(par[i][u]!=par[i][v])
            u = par[i][u], v = par[i][v];
    return par[0][u];
}

void DP(int v, int msk) {
    if(dp[v][msk] != -1) return;
    if(!(mask[t] & msk)) {
        dp[v][msk] = dest[v];
        return;
    }
    dp[v][msk] = inf;
    for(int i=0; i<timer; i++) if(msk>>i&1)
        if(!((mask[key[i]]|mask[door[i]]) & msk)) {
            DP(i, msk^(1<<i));
            mins(dp[v][msk], dp[i][msk^(1<<i)] + dis[v][i]);
        }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> s >> t;
    for(int i=0; i<n-1; i++) {
        cin >> U[i] >> V[i] >> W[i];
        if(W[i]==0) W[i] = -1;
        else key[W[i]=timer++] = W[i];
        g[U[i]].push_back(i);
        g[V[i]].push_back(i);
    }
    door[timer] = s;
    dfs(s);
    for(int i=0; i<=timer; i++) {
        for(int j=0; j<timer; j++) if(i^j)
            dis[i][j] = h[door[i]] + 2*h[key[j]] + h[door[j]]
                      - 2*h[LCA(door[i], key[j])] - 2*h[LCA(key[j], door[j])];
        dest[i] = h[door[i]] + h[t] - 2*h[LCA(door[i], t)];
    }
    memset(dp, -1, sizeof(dp));
    DP(timer, (1<<timer)-1);
    cout << (dp[timer][(1<<timer)-1]==inf ? -1 : dp[timer][(1<<timer)-1]) << '\n';
    return 0;
}

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