Submission #635735

#	Time	Username	Problem	Language	Result	Execution time	Memory
635735		MohammadAghil	LOSTIKS (INOI20_lostiks)	C++17	59 / 100	2102 ms	122024 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define ff first
#define ss second

void dbg(){
    cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
    cerr << " " << h << ",";
    dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
//    #ifndef ONLINE_JUDGE
//        freopen("inp.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
//    #endif
}

const ll mod = 1e9 + 7, maxn = 1e6 + 5, maxm = 20, inf = ll(1e9) + 5;

int val[maxn], ed[maxm], nxt[maxm], tmp, n;
vector<pp> adj[maxn];

void dfs(int r, int p){
    val[r] |= val[p];
    for(auto&[c, w]: adj[r]) if(c - p){
        if(w + 1){
            ed[tmp] = r;
            nxt[tmp] = w;
            val[c] = 1<<tmp;
            tmp++;
            dfs(c, r);
        } else{
            dfs(c, r);
        }
    }
}

int dist[maxm + 1][maxn], dq[maxn], st, en, tmp_vl[maxm][maxm];

void dfs2(int r, int id){
//    vector<pp> stk;
//    for(auto&[c, w]: adj[r]) if(c - p){
//        dist[id][c] = dist[id][r] + 1;
//        dfs2(c, r);
//    }
    dq[st = 0]  = r, en = 1;
    fill(dist[id], dist[id] + n, -1);
    dist[id][r] = 0;
    while(st < en){
        int r = dq[st++];
        for(auto&[c, w]: adj[r]) if(dist[id][c] == -1){
            dist[id][c] = dist[id][r] + 1;
            dq[en++] = c;
        }
    }
}

int dp[maxm][1<<maxm];

int main(){ IOS();
    int s, t; cin >> n >> s >> t; s--, t--;
    int m = 0;
    rep(i,1,n){
        int u, v, w; cin >> u >> v >> w; u--, v--, w--;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        m += w != -1;
    }
    dfs(s, -1);
    rep(i,0,m){
        dfs2(ed[i], i);
    }
    dfs2(s, m);

    rep(i,0,m){
        rep(j,0,m){
            tmp_vl[i][j] = dist[i][nxt[j]] + dist[j][nxt[j]];
        }
    }

    auto chk = [&](int msk, int r){
        return (val[r]&msk) == val[r];
    };
    vector<int> is(m), nis(m);
    int ptr_is = 0, ptr_nis = 0;
    per(i,(1<<m)-1,1){
        ptr_is = ptr_nis = 0;
        rep(e,0,m) {
            if(i>>e&1){
                if(chk(i, ed[e])) is[ptr_is++] = e;
            }else{
                if(chk(i, nxt[e]) && chk(i, ed[e])) nis[ptr_nis++] = e;
            }
        }
        rep(x,0,ptr_is){
            int e = is[x];
            dp[e][i] = inf;
            if(chk(i, t)){
                dp[e][i] = dist[e][t];
            }else{
                rep(j,0,ptr_nis){
                    dp[e][i] = min(dp[e][i], dp[nis[j]][i^(1<<nis[j])] + tmp_vl[e][nis[j]]);
                }
            }
        }
    }
    int ans = inf;
    rep(i,0,m){
        if(chk(0, nxt[i]) && chk(0, ed[i])) ans = min(ans, dp[i][1<<i] + dist[m][nxt[i]] + dist[i][nxt[i]]);
    }
    if(chk(0, t)){
        ans = dist[m][t];
    }
    cout << (ans == inf? -1: ans) << '\n';
    return 0;
}

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