Submission #953879

#	Time	Username	Problem	Language	Result	Execution time	Memory
953879		angella	LOSTIKS (INOI20_lostiks)	C++17	100 / 100	1544 ms	250300 KiB

Main

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 1e6+23, lg = 20;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, s, t, m, tim, nd[22][22], dp[(1<<20)][21], par[lg][N];
int arr[22][5], mark[N], h[N], dst[22][22], tin[N], tout[N];
vector<int> adj[N];

void init(int v, int p=0) {
    tin[v] = ++tim, par[0][v] = p, h[v] = h[p] + 1;
    for(int i=1; i<lg; i++) par[i][v] = par[i-1][par[i-1][v]];
    for(int u : adj[v]) {
        if(u == p) continue;
        init(u, v);
    }
    tout[v] = tim+1;
}

int getPar(int v, int dist) {
    for(int i=0; i<lg; i++) if((dist>>i)%2 == 1) v = par[i][v];
    return v;
}

int LCA(int v, int u) {
    if(h[v] > h[u]) swap(v, u);
    u = getPar(u, h[u] - h[v]);
    if(v == u) return v;
    for(int i=lg-1; i>=0; i--) {
        if(par[i][v] != par[i][u]) {
            v = par[i][v], u = par[i][u];
        }
    }
    return par[0][v];
}

int calc(int v, int u) {
    int lca = LCA(v, u);
    return h[v]+h[u]-2*h[lca];
}

bool insub(int v, int u) {
    if(tin[v] <= tin[u] && tout[v] > tin[u]) return true;
    return false;
}

bool isinpath(int w, int v, int u) {
    int lca = LCA(v, u);
    if(insub(lca,w)==1&&(insub(w,v)==1||insub(w,u)==1)) return 1;
    return 0;
}

int calc2(int v, int u) {
    int res = 0;
    for(int i=1; i<=m; i++) {
        if(isinpath(arr[i][4],v,u)==1) {
            res |= (1<<(i-1));
        }
    }
    return res;
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>s>>t;
    for(int v,u,w,i=1; i<n; i++) {
        cin>>v>>u>>w;
        adj[v].pb(u); adj[u].pb(v);
        if(w > 0) {
            m++;
            arr[m][3]=w, arr[m][0]=v, arr[m][1]=u;
        }
    }

    init(1);
    for(int i=1; i<=m; i++) {
        if(calc(arr[i][0], s) < calc(arr[i][1], s)) {
            arr[i][2] = arr[i][0];
            arr[i][4] = arr[i][1];
        } else {
            arr[i][2] = arr[i][1];
            arr[i][4] = arr[i][0];
        }
        mark[arr[i][4]] = 1;
    }
    if(calc2(s, t) == 0) kill(calc(s, t));
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=m; j++) {
            dst[i][j] = calc(arr[i][2], arr[j][3]) + calc(arr[j][3], arr[j][2]);
            nd[i][j] = (calc2(arr[i][2], arr[j][3]) | calc2(arr[j][3], arr[j][2]));
        }
        nd[0][i] = (calc2(s, arr[i][2]) | calc2(s, arr[i][3]));
        nd[i][m+1] = calc2(arr[i][2], t);
    }

    for(int i=0; i<=m+1; i++) {
        for(int j=0; j<=m+1; j++) {
            int v = (i==0?s:(i==m+1?t:arr[i][2]));
            int u = (j==0?s:(j==m+1?t:arr[j][2]));
            if(i!=0 && i!=m+1 && j!=0 && j!=m+1) continue;
            if(i==0&&j<=m) {
    dst[i][j] = calc(v, arr[j][3]) + calc(arr[j][3], arr[j][2]);
            } else {
    dst[i][j] = calc(v, u);
            }
        }
    }

    for(int i=0; i<(1<<m); i++) fill(dp[i],dp[i]+21,1e9);
    for(int i=1; i<=m; i++) {
        if(nd[0][i] == 0) {
            dp[(1<<(i-1))][i] = dst[0][i];
        }
    }
    //fuck(nd[1][1]);

    int ans = 1e9;
    for(int mask=1; mask<(1<<m); mask++) {
        for(int i=1; i<=m; i++) {
        if((mask>>(i-1))%2==0) continue;
        if(__builtin_popcount(mask) > 1) {
            dp[mask][i] = 1e9;
            int mask2 = mask - (1<<(i-1));
            for(int j=1; j<=m; j++) {
                if((mask2>>(j-1))%2==0) continue; 
                //int mask3 = mask2 - (1<<(j-1));
                if((nd[j][i]&mask2) == nd[j][i]) {
                    dp[mask][i] = min(dp[mask][i], dp[mask2][j]+dst[j][i]);
                }
            }
        }
    if(mark[t] == 1)  {
        if(arr[i][4]==t)ans = min(ans, dp[mask][i]+1); 
    } else if((nd[i][m+1]&mask)==nd[i][m+1]) ans = min(ans, dp[mask][i]+dst[i][m+1]);
        }
    }
    //fuck(nd[1][2]);

    cout<<(ans==1e9 ? -1 : ans)<<endl;

	return 0;
}

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