Submission #635750

#	Time	Username	Problem	Language	Result	Execution time	Memory
635750		MohammadAghil	LOSTIKS (INOI20_lostiks)	C++17	100 / 100	1399 ms	184876 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


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, lg = 20, inf = ll(1e9) + 5;

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

int par[maxn][lg], h[maxn];

void dfs(int r){

    rep(i,0,lg) par[r][i] = r;
    dq[st = 0] = r, en = 1;
    while(st < en){
        int r = dq[st++];
        rep(i,1,lg) par[r][i] = par[par[r][i-1]][i-1];
        for(auto&[c, w]: adj[r]) if(c - par[r][0]){
            val[c] = val[r];
            h[c] = h[r] + 1;
            par[c][0] = r;
            if(w + 1){
                ed[tmp] = r;
                nxt[tmp] = w;
                val[c] |= 1<<tmp;
                tmp++;
            }
            dq[en++] = c;
        }
    }


//    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);
//        }
//    }
}


//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 lca(int u, int v){
    if(h[u] > h[v]) swap(u, v);
    per(i,lg-1,0) if(h[par[v][i]] >= h[u]) v = par[v][i];
    if(u == v) return u;
    per(i,lg-1,0) if(par[u][i] - par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
}

int dist(int u, int v){
    return h[u] + h[v] - (h[lca(u, v)]<<1);
}

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

int main(){ IOS();
    // tof to zatet ba in limitaie soal
    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);
//    rep(i,0,m){
//        dfs2(ed[i], i);
//    }
//    dfs2(s, m);

    rep(i,0,m){
        rep(j,0,m){
            tmp_vl[i][j] = dist(ed[i], nxt[j]) + dist(ed[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(ed[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(s, nxt[i]) + dist(ed[i], nxt[i]));
    }
    if(chk(0, t)){
        ans = dist(s, t);
    }
    cout << (ans == inf? -1: ans) << '\n';
    return 0;
}

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