답안 #953839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953839 2024-03-26T17:55:48 Z angella LOSTIKS (INOI20_lostiks) C++17
0 / 100
71 ms 76736 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++) {
        for(int i=1; i<=m; i++) {
        if((mask>>(i-1))%2==0) {
            dp[mask][i] = 1e9;
            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((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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 70228 KB Output is correct
2 Correct 11 ms 70236 KB Output is correct
3 Correct 56 ms 74724 KB Output is correct
4 Correct 58 ms 75004 KB Output is correct
5 Correct 56 ms 74836 KB Output is correct
6 Correct 52 ms 74580 KB Output is correct
7 Correct 59 ms 76736 KB Output is correct
8 Correct 60 ms 74836 KB Output is correct
9 Correct 71 ms 74836 KB Output is correct
10 Correct 53 ms 76464 KB Output is correct
11 Correct 57 ms 74580 KB Output is correct
12 Incorrect 54 ms 75480 KB Output isn't correct
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 70232 KB Output is correct
2 Correct 11 ms 70232 KB Output is correct
3 Correct 11 ms 68444 KB Output is correct
4 Incorrect 10 ms 60248 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 70228 KB Output is correct
2 Correct 11 ms 70236 KB Output is correct
3 Correct 56 ms 74724 KB Output is correct
4 Correct 58 ms 75004 KB Output is correct
5 Correct 56 ms 74836 KB Output is correct
6 Correct 52 ms 74580 KB Output is correct
7 Correct 59 ms 76736 KB Output is correct
8 Correct 60 ms 74836 KB Output is correct
9 Correct 71 ms 74836 KB Output is correct
10 Correct 53 ms 76464 KB Output is correct
11 Correct 57 ms 74580 KB Output is correct
12 Incorrect 54 ms 75480 KB Output isn't correct
13 Halted 0 ms 0 KB -