답안 #953818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953818 2024-03-26T17:36:18 Z angella LOSTIKS (INOI20_lostiks) C++17
0 / 100
70 ms 83024 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<<endl;

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 70232 KB Output is correct
2 Correct 11 ms 70408 KB Output is correct
3 Correct 56 ms 82256 KB Output is correct
4 Correct 58 ms 82256 KB Output is correct
5 Correct 54 ms 82260 KB Output is correct
6 Correct 54 ms 82108 KB Output is correct
7 Correct 61 ms 82344 KB Output is correct
8 Correct 67 ms 82356 KB Output is correct
9 Correct 54 ms 82460 KB Output is correct
10 Correct 54 ms 82172 KB Output is correct
11 Correct 70 ms 82304 KB Output is correct
12 Incorrect 50 ms 83024 KB Output isn't correct
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 70232 KB Output is correct
2 Correct 11 ms 70232 KB Output is correct
3 Correct 11 ms 70420 KB Output is correct
4 Incorrect 11 ms 70376 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 70232 KB Output is correct
2 Correct 11 ms 70408 KB Output is correct
3 Correct 56 ms 82256 KB Output is correct
4 Correct 58 ms 82256 KB Output is correct
5 Correct 54 ms 82260 KB Output is correct
6 Correct 54 ms 82108 KB Output is correct
7 Correct 61 ms 82344 KB Output is correct
8 Correct 67 ms 82356 KB Output is correct
9 Correct 54 ms 82460 KB Output is correct
10 Correct 54 ms 82172 KB Output is correct
11 Correct 70 ms 82304 KB Output is correct
12 Incorrect 50 ms 83024 KB Output isn't correct
13 Halted 0 ms 0 KB -