oj.uz

답안 #953836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953836 2024-03-26T17:54:08 Z angella LOSTIKS (INOI20_lostiks) C++17
0 / 100
 64 ms 75888 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) 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;
}

Subtask #1
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 66136 KB Output is correct
2 Correct 10 ms 64088 KB Output is correct
3 Correct 56 ms 71364 KB Output is correct
4 Correct 64 ms 71720 KB Output is correct
5 Correct 58 ms 74692 KB Output is correct
6 Correct 53 ms 74568 KB Output is correct
7 Correct 55 ms 75848 KB Output is correct
8 Correct 55 ms 75860 KB Output is correct
9 Correct 56 ms 75844 KB Output is correct
10 Correct 58 ms 75888 KB Output is correct
11 Correct 55 ms 75600 KB Output is correct
12 Incorrect 59 ms 74940 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 66136 KB Output is correct
2 Correct 10 ms 59996 KB Output is correct
3 Correct 10 ms 62300 KB Output is correct
4 Incorrect 10 ms 60252 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 66136 KB Output is correct
2 Correct 10 ms 64088 KB Output is correct
3 Correct 56 ms 71364 KB Output is correct
4 Correct 64 ms 71720 KB Output is correct
5 Correct 58 ms 74692 KB Output is correct
6 Correct 53 ms 74568 KB Output is correct
7 Correct 55 ms 75848 KB Output is correct
8 Correct 55 ms 75860 KB Output is correct
9 Correct 56 ms 75844 KB Output is correct
10 Correct 58 ms 75888 KB Output is correct
11 Correct 55 ms 75600 KB Output is correct
12 Incorrect 59 ms 74940 KB Output isn't correct
13 Halted 0 ms 0 KB -