답안 #953842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953842 2024-03-26T17:57:47 Z angella LOSTIKS (INOI20_lostiks) C++17
0 / 100
65 ms 73124 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=0; i<(1<<m); i++) fill(dp[i],dp[i]+21,1e9);
    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) {
            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 11 ms 68184 KB Output is correct
2 Correct 10 ms 62492 KB Output is correct
3 Correct 65 ms 67924 KB Output is correct
4 Correct 54 ms 68184 KB Output is correct
5 Correct 54 ms 73044 KB Output is correct
6 Correct 53 ms 73092 KB Output is correct
7 Correct 62 ms 71344 KB Output is correct
8 Correct 58 ms 71472 KB Output is correct
9 Correct 55 ms 73040 KB Output is correct
10 Correct 59 ms 73124 KB Output is correct
11 Correct 54 ms 73040 KB Output is correct
12 Incorrect 51 ms 72276 KB Output isn't correct
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 68184 KB Output is correct
2 Correct 11 ms 68296 KB Output is correct
3 Correct 10 ms 62296 KB Output is correct
4 Incorrect 11 ms 66396 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 68184 KB Output is correct
2 Correct 10 ms 62492 KB Output is correct
3 Correct 65 ms 67924 KB Output is correct
4 Correct 54 ms 68184 KB Output is correct
5 Correct 54 ms 73044 KB Output is correct
6 Correct 53 ms 73092 KB Output is correct
7 Correct 62 ms 71344 KB Output is correct
8 Correct 58 ms 71472 KB Output is correct
9 Correct 55 ms 73040 KB Output is correct
10 Correct 59 ms 73124 KB Output is correct
11 Correct 54 ms 73040 KB Output is correct
12 Incorrect 51 ms 72276 KB Output isn't correct
13 Halted 0 ms 0 KB -