Submission #1266789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266789		bb8	LOSTIKS (INOI20_lostiks)	C++20	59 / 100	2082 ms	145160 KiB

Main

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
#define F first
#define S second

const int N = 1e6 + 60;
const int MSK = (1<<20) + 60;
const int M = 24;
const int INF = 1e9 + 9;
ll mvcnt = 0;

vector <int> adj[N];
int key[M];
int lok[M];
int Disk[M][N];
int Wk[M][M];//key -> lock
int dp[M][MSK];
int eg[M];
int teg[M][2];
int Wisk[N];
int Dt[N];

struct  tii{
    int u;
    int v;
    int w;
};

int ck = 0;
int cms = 0;
int n, s, t;
void dfs(int u, int fa){
    //mvcnt++;
    Disk[ck][u] = Disk[ck][fa] + 1;
    if (u > n){
        Disk[ck][u]--;
        cms |= (1<<(u-n-1));
        Wk[ck][u-n-1] = cms;
    }
    for (int v:adj[u]){
        mvcnt++;
        if (v != fa)
            dfs(v, u);
    }
    if (u > n)
        cms ^= (1<<(u-n-1));
}

void dtfs(int u, int fa){
    //mvcnt++;
    Wisk[u] = Wisk[fa];
    Dt[u] = Dt[fa] + 1;
    if (u > n){
        Dt[u]--;
        Wisk[u] |= (1<<(u-n-1));
    }
    for (int v:adj[u]){
        //mvcnt++;
        if (v != fa)
            dtfs(v, u);
    }
}

vector <tii> q;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s >> t;
    int k = 0;
    for (int i=1;i<n;i++){
        int u, v, w;
        cin >> u >> v >> w;
        if (w == 0)
            w = -1;
        q.push_back({u, v, w});
    }
    for (auto [u, v, w]:q){
        if (w != -1){
            mvcnt++;
            key[k] = w;
            teg[k][0] = u;
            teg[k][1] = v;
            k++;
            adj[u].push_back(n+k); adj[n+k].push_back(u);
            adj[n+k].push_back(v); adj[v].push_back(n+k);
        }
        else {
            adj[u].push_back(v); adj[v].push_back(u);
        }
    }
    Dt[n+k+1] = -1;
    dtfs(s, n+k+1);
    for (int i=0;i<k;i++){
        if (Dt[teg[i][0]] > Dt[teg[i][1]])
            eg[i] = teg[i][1];
        else
            eg[i] = teg[i][0];
    }
    for (int i=0;i<k;i++){
        ck = i;
        Disk[i][n+k+1] = -1;
        dfs(key[i], n+k+1);
    }
    Dt[n+k+1] = -1;
    dtfs(t, n+k+1);
    int msk = 1 << k;
    int mvvv = 0;
    for (int ms=msk-1;ms>0;ms--){ //msk //i: eg[i] <- ma & klid haye msk ro dareim
        int ci = ms;
        mvvv++;
        while (ci){
            mvvv += 3;
            int i = __builtin_ctz(ci);
            ci ^= (1 << i);
            if ((Wisk[eg[i]] & ms) == Wisk[eg[i]]){
                dp[i][ms] = Dt[eg[i]];
                continue;
            }
            mvvv += 2;
            dp[i][ms] = INF;
            int cm = msk - 1 - ms;
            while (cm){
                mvvv += 5;
                int j = __builtin_ctz(cm);
                int jb = (1 << j);
                cm ^= jb;
                if (((Wk[j][i] & ms) == Wk[j][i]) && ((Wk[j][j] & (ms|jb)) == Wk[j][j]))
                    dp[i][ms] = min(dp[i][ms], Disk[j][eg[i]] + Disk[j][eg[j]] + dp[j][ms | jb]);
            }
        }
    }
    dtfs(s, n+k+1);
    if (Wisk[t] == 0){
        cout << Dt[t] << '\n';
        return 0;
    }
    int ans = INF;
    for (int i=0;i<k;i++){
        int sb = Wisk[eg[i]];
        if (Wisk[key[i]] == 0 && (sb & (1 << i)) == sb){
            ans = min(ans, dp[i][1<<i] + Disk[i][s] + Disk[i][eg[i]]);
        }
    }
    //mvcnt /= 10000000;
    ///exit(mvcnt);
    if (ans == INF)
        cout << -1 << '\n';
    else
        cout << ans << '\n';
}

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