Submission #1292904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292904		BuiDucManh123	LOSTIKS (INOI20_lostiks)	C++20	23 / 100	137 ms	173728 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define taskname ""
#define ld long double
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const ll INFLL = (ll)4e18;

int main(){
    if (fopen(taskname".inp","r")) {
        freopen(taskname".inp","r",stdin);
        freopen(taskname".out","w",stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, s, t;
    cin >> n >> s >> t;
    struct Edge { int to; int keyroom; };
    vector<vector<Edge>> g(n+1);
    vector<int> keyvals;
    for (int i = 0; i < n-1; ++i){
        int u,v,w; cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        if (w != 0) keyvals.pb(w);
    }
    keyvals.pb(0);
    sort(keyvals.begin(), keyvals.end());
    keyvals.erase(unique(keyvals.begin(), keyvals.end()), keyvals.end());
    int sz = (int)keyvals.size();
    if (sz > 22){
        cout << -1 << '\n';
        return 0;
    }
    unordered_map<int,int> trace;
    trace.reserve(sz*2);
    for (int i = 0; i < sz; ++i) trace[keyvals[i]] = i;
    vector<int> parent(n+1,0), depth(n+1,0), summask(n+1,0);
    vector<int> door_room(sz, -1);
    parent[s] = s;
    depth[s] = 0;
    summask[s] = 0;
    door_room[trace[0]] = s;
    vector<int> st;
    st.push_back(s);
    while(!st.empty()){
        int u = st.back(); st.pop_back();
        for (auto &e : g[u]){
            int v = e.to;
            int w = e.keyroom;
            if (v == parent[u]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            summask[v] = summask[u];
            if (w != 0){
                int idx = trace[w];
                door_room[idx] = u;
                summask[v] |= (1 << idx);
            }
            st.push_back(v);
        }
    }
    int lg = 1;
    while ((1<<lg) <= n) ++lg;
    vector<vector<int>> up(lg, vector<int>(n+1));
    for (int v = 1; v <= n; ++v) up[0][v] = parent[v];
    for (int i = 1; i < lg; ++i) for (int v = 1; v <= n; ++v) up[i][v] = up[i-1][ up[i-1][v] ];
    auto lca = [&](int a, int b){
        if (depth[a] < depth[b]) swap(a,b);
        int diff = depth[a] - depth[b];
        for (int i = 0; i < lg; ++i) if (diff & (1<<i)) a = up[i][a];
        if (a == b) return a;
        for (int i = lg-1; i >= 0; --i) if (up[i][a] != up[i][b]) { a = up[i][a]; b = up[i][b]; }
        return up[0][a];
    };
    vector<int> keynode = keyvals;
    int idx0 = trace[0];
    if (idx0 != 0){
        swap(keynode[0], keynode[idx0]);
        swap(door_room[0], door_room[idx0]);
    }
    keynode[0] = s;
    door_room[0] = s;
    vector<int> dis2(sz,0);
    for (int i = 0; i < sz; ++i){
        int u = keynode[i], v = door_room[i];
        int w = lca(u,v);
        dis2[i] = depth[u] + depth[v] - 2*depth[w];
    }
    vector<vector<int>> dis1(sz, vector<int>(sz,0));
    for (int i = 0; i < sz; ++i) for (int j = 0; j < sz; ++j){
        int v = door_room[i], vv = keynode[j];
        int w = lca(v,vv);
        dis1[i][j] = depth[v] + depth[vv] - 2*depth[w];
    }
    int FULL = 1<<sz;
    vector<vector<ll>> dp(sz, vector<ll>(FULL, INFLL));
    dp[0][1] = 0;
    for (int mask = 1; mask < FULL; ++mask){
        for (int i = 0; i < sz; ++i){
            if (dp[i][mask] == INFLL) continue;
            for (int j = 1; j < sz; ++j){
                if ((mask>>j) & 1) continue;
                int u = keynode[j], v = door_room[j];
                int path1 = summask[ door_room[i] ] ^ summask[u];
                int path2 = summask[v] ^ summask[u];
                if ((mask & path1) == path1 && (mask & path2) == path2){
                    int nm = mask | (1<<j);
                    ll cost = dp[i][mask] + (ll)dis1[i][j] + (ll)dis2[j];
                    if (cost < dp[j][nm]) dp[j][nm] = cost;
                }
            }
        }
    }
    ll ans = INFLL;
    for (int mask = 0; mask < FULL; ++mask) for (int i = 0; i < sz; ++i){
        if (dp[i][mask] == INFLL) continue;
        int u = door_room[i];
        int path = summask[u] ^ summask[t];
        int w = lca(u,t);
        if ((mask & path) == path){
            ll total = dp[i][mask] + (ll)(depth[u] + depth[t] - 2*depth[w]);
            if (total < ans) ans = total;
        }
    }
    if (ans == INFLL) cout << -1;
    else cout << ans;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(taskname".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen(taskname".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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