Submission #953830

# Submission time Handle Problem Language Result Execution time Memory
953830 2024-03-26T17:46:52 Z angella LOSTIKS (INOI20_lostiks) C++17
0 / 100
70 ms 83028 KB
/*
    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], 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];
        }
    }
    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]));
            
            if(i==j) continue;
        }
        nd[0][i] = calc2(s, arr[i][2]);
        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=1; i<=m; i++) {
        dp[(1<<(i-1))][i] = 1e9;
        if(nd[0][i] == 0) {
            dp[(1<<(i-1))][i] = dst[0][i];
        }
    }

    int ans = 1e9;
    for(int mask=1; mask<(1<<m); mask++) {
        if(__builtin_popcount(mask) == 1) continue;
        for(int i=1; i<=m; i++) {
            dp[mask][i] = 1e9;
            if((mask>>(i-1))%2==0) continue;
            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((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;
}
# Verdict Execution time Memory Grader output
1 Correct 33 ms 70236 KB Output is correct
2 Correct 13 ms 70232 KB Output is correct
3 Correct 55 ms 82276 KB Output is correct
4 Correct 54 ms 82256 KB Output is correct
5 Correct 55 ms 82256 KB Output is correct
6 Correct 55 ms 82288 KB Output is correct
7 Correct 61 ms 82260 KB Output is correct
8 Correct 59 ms 82272 KB Output is correct
9 Correct 70 ms 82284 KB Output is correct
10 Correct 59 ms 82260 KB Output is correct
11 Correct 54 ms 82256 KB Output is correct
12 Incorrect 64 ms 83028 KB Output isn't correct
13 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 11 ms 70236 KB Output is correct
2 Correct 11 ms 70232 KB Output is correct
3 Correct 11 ms 70488 KB Output is correct
4 Incorrect 11 ms 70364 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 33 ms 70236 KB Output is correct
2 Correct 13 ms 70232 KB Output is correct
3 Correct 55 ms 82276 KB Output is correct
4 Correct 54 ms 82256 KB Output is correct
5 Correct 55 ms 82256 KB Output is correct
6 Correct 55 ms 82288 KB Output is correct
7 Correct 61 ms 82260 KB Output is correct
8 Correct 59 ms 82272 KB Output is correct
9 Correct 70 ms 82284 KB Output is correct
10 Correct 59 ms 82260 KB Output is correct
11 Correct 54 ms 82256 KB Output is correct
12 Incorrect 64 ms 83028 KB Output isn't correct
13 Halted 0 ms 0 KB -