제출 #1292905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292905		BuiDucManh123	LOSTIKS (INOI20_lostiks)	C++20	100 / 100	1036 ms	361660 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 E{int to; int kid;};
    vector<vector<E>> g(n+1);
    int curk = 0;
    vector<int> keyroom(1,0);
    for(int i=0;i<n-1;i++){
        int u,v,w; cin>>u>>v>>w;
        int kid = 0;
        if(w!=0){
            curk++;
            keyroom.pb(w);
            kid = curk;
        }
        g[u].push_back({v,kid});
        g[v].push_back({u,kid});
    }
    int M = curk;
    int sz = M + 1;
    if (sz > 23){ cout << -1 << '\n'; return 0; }
    vector<int> parent(n+1,0), depth(n+1,0), summask(n+1,0);
    vector<int> door_room(sz, -1), keynode(sz, -1);
    keynode[0] = s;
    door_room[0] = s;
    parent[s] = s;
    depth[s] = 0;
    summask[s] = 0;
    vector<int> st; st.pb(s);
    while(!st.empty()){
        int u = st.back(); st.pop_back();
        for(auto &e: g[u]){
            int v = e.to;
            if(v == parent[u]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            summask[v] = summask[u];
            if(e.kid != 0){
                int k = e.kid;
                door_room[k] = u;
                keynode[k] = keyroom[k];
                summask[v] |= (1<<k);
            }
            st.pb(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];
    };
    for(int k=1;k<=M;k++){
        if(door_room[k] == -1){
            cout << -1 << '\n';
            return 0;
        }
    }
    vector<int> dis2(sz,0);
    for(int i=0;i<sz;i++){
        int u = keynode[i];
        int v = door_room[i];
        if(u == -1){ dis2[i] = 0; continue; }
        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];
        if(vv == -1){ dis1[i][j] = 0; continue; }
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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