Submission #1208270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208270		alir3za_zar3	LOSTIKS (INOI20_lostiks)	C++20	100 / 100	786 ms	378956 KiB

Main

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define     int     long long

const int maxn = 1e6+7 , maxm = 21;
const int inF  = 1e9;
int n,s,t,q , dp[maxm][1<<maxm],p[maxm][maxn];
int len[maxm][maxm] , qmsk[maxn] , dep[maxn];
int f[maxm] , key[maxm] , door[maxm];
vector<pair<int,int>> e[maxn];

void dfs (int v)
{
    for (auto [u , lock] : e[v])
        if (u != p[0][v])
        {
            p[0][u] = v , dep[u] = dep[v]+1;
            if (lock) 
                qmsk[u] = 1<<lock-1 , door[lock-1] = v;
            qmsk[u] |= qmsk[v];
            dfs(u);
        }
}

int lca (int v , int u)
{
    if (dep[v] < dep[u]) swap(v , u);
    int k = dep[v] - dep[u];
    for (int bit=0; bit<maxm; bit++)
        if ((1<<bit)&k) v = p[bit][v];
    if (v == u) return v;
    for (int bit=maxm-1; bit>=0; bit--)
        if (p[bit][v] != p[bit][u])
            v = p[bit][v] , u = p[bit][u];
    return p[0][v];
}

void calc_dp (int v , int msk)
{
    if (dp[v][msk] != -1) return;
    if (!(msk & qmsk[t]))
    {
        dp[v][msk] = f[v]; return;
    }
    dp[v][msk] = inF;
    for (int k=0; k<q; k++)
        if ((1<<k)&msk)
        {
            int vmsk = qmsk[key[k]]|qmsk[door[k]];
            if (!(vmsk & msk))
                calc_dp(k , msk ^ (1<<k)) ,\
                dp[v][msk] = min(dp[v][msk] , dp[k][msk^(1<<k)]+len[v][k]);
        }
}

signed main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
    
    cin >> n >> s >> t;
    for (int i=1; i<n; i++)
    {
        int u,v,k; cin >> u >> v >> k;
        if (k) key[q++] = k , k=q;
        e[v].push_back({ u , k });
        e[u].push_back({ v , k });
    }
    door[q] = s;
    dfs(s); p[0][s] = s;
    for (int i=1; i<maxm; i++)
        for (int v=1; v<=n; v++)
            p[i][v] = p[i-1][p[i-1][v]];
    for (int i=0; i<=q; i++)
        for (int j=0; j<q; j++)
        {
            int l0 = lca(door[i] , key[j]);
            int l1 = lca(key[j] , door[j]);
            len[i][j] = dep[door[i]]+dep[key[j]]*2+dep[door[j]]
                      - dep[l0]*2 - dep[l1]*2;
        }
    for (int i=0; i<=q; i++)
    {
        int l = lca(door[i] , t);
        f[i] = dep[door[i]]+dep[t]-dep[l]*2;
    }

    memset(dp , -1 , sizeof(dp));
    calc_dp(q , (1<<q)-1);
    if (dp[q][(1<<q)-1] == inF)
        cout << -1 << '\n';
    else 
        cout << dp[q][(1<<q)-1] << '\n';
}

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