Submission #1261638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261638		Hamed_Ghaffari	LOSTIKS (INOI20_lostiks)	C++20	0 / 100	60 ms	31812 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;
vector<pii> g[MXN];
int dis[MXM+2][MXN], dp[1<<MXM][MXM], id[MXN], mask[MXN];
vector<int> vec;

void dfs_dis(int wh, int v, int p=0) {
    for(auto [u, w] : g[v])
        if(u!=p) {
            dis[wh][u] = dis[wh][v]+1;
            dfs_dis(wh, u, v);
        }
}

void dfs(int v, int p=0) {
    for(auto [u, w] : g[v])
        if(u!=p) {
            mask[u] = mask[v] | (w ? (1<<id[w]) : 0);
            dfs(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);
    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) vec.push_back(w);
    }
    sort(vec.begin(), vec.end());
    m = unique(vec.begin(), vec.end())-vec.begin();
    vec.resize(m);
    for(int i=0; i<m; i++)
        dfs_dis(id[vec[i]]=i, vec[i]);
    dfs_dis(m, s);
    dfs_dis(m+1, t);
    dfs(s);
    if(!mask[t]) {
        cout << dis[m][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[vec[i]])
            dp[1<<i][i] = dis[m][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))
                if(is_sub(mask[vec[i]]|mask[vec[j]], msk))
                    mins(dp[msk^(1<<j)][j], dp[msk][i] + dis[i][vec[j]]);
    int ans = inf;
    for(int msk=1; msk<(1<<m); msk++) if(is_sub(mask[t], msk))
        for(int i=0; i<m; i++) if(msk>>i&1)
            mins(ans, dp[msk][i] + dis[m+1][vec[i]]);
    cout << ans << '\n';
    return 0;
}

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