Submission #1261665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261665		Hamed_Ghaffari	LOSTIKS (INOI20_lostiks)	C++20	23 / 100	479 ms	72112 KiB

Main

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

using pii = pair<int, int>;

#define X first
#define Y second
#define mins(a, b) (a = min(a,b))

const int MXN = 1e6+2, MXM = 20, inf = 1e9;

int n, m, s, t, ctr, id[MXN], vec[MXN];
vector<pii> g[MXN];
int dis[MXM*2+1][MXN], dp[1<<MXM][MXM], mask[MXM*2+1][MXN], door[MXN];

inline void assign_id(int v) {
    if(id[v]==-1)
        vec[id[v]=ctr++] = v;
}

void dfs1(int v, int p=0) {
    for(auto [u, w] : g[v])
        if(u!=p) {
            if(w) {
                door[w] = v;
                assign_id(v);
            }
            dfs1(u, v);
        }
}

void dfs(int wh, int v, int p=0) {
    for(auto [u, w] : g[v])
        if(u!=p) {
            dis[wh][u] = dis[wh][v]+1;
            mask[wh][u] = mask[wh][v] | (w ? (1<<id[w]) : 0);
            dfs(wh, u, v);
        }
}

inline bool is_sub(int x, int y) { return (x&y)==x; }

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    memset(id, -1, sizeof(id));
    cin >> n >> s >> t;
    for(int i=0, u,v,w; i<n-1; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        if(w) assign_id(w);
    }
    m = ctr;
    dfs1(s);
    assign_id(s);
    for(int i=0; i<ctr; i++) dfs(i, vec[i]);
    if(!mask[id[s]][t]) {
        cout << dis[id[s]][t] << '\n';
        return 0;
    }
    for(int msk=0; msk<(1<<m); msk++)
        fill(dp[msk], dp[msk]+m, inf);
    for(int i=0; i<m; i++)
        if(!mask[id[s]][vec[i]] && !mask[i][door[vec[i]]])
            dp[1<<i][i] = dis[id[s]][vec[i]] + dis[i][door[vec[i]]];
    for(int msk=1; msk<(1<<m)-1; msk++)
        for(int i=0; i<m; i++) if(msk>>i&1)
            for(int j=0; j<m; j++) if(!(msk>>j&1)) {
                int v = door[vec[i]], u = vec[j], w = door[vec[j]];
                if(is_sub(mask[id[v]][u], msk) && is_sub(mask[id[u]][w], msk))
                    mins(dp[msk^(1<<j)][j], dp[msk][i] + dis[id[v]][u] + dis[id[u]][w]);
            }
    int ans = inf;
    for(int msk=1; msk<(1<<m); msk++)
        for(int i=0; i<m; i++) if((msk>>i&1) && is_sub(mask[id[door[vec[i]]]][t], msk))
            mins(ans, dp[msk][i] + dis[id[door[vec[i]]]][t]);
    cout << (ans==inf ? -1 : ans) << '\n';
    return 0;
}

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