Submission #999276

#	Time	Username	Problem	Language	Result	Execution time	Memory
999276		vjudge1	LOSTIKS (INOI20_lostiks)	C++17	0 / 100	169 ms	96540 KiB

Main

#include <bits/stdc++.h>

#define int long long
// #define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e18 + 9;
const int MAX = 1e6 + 5, LOGMAX = 20, B = 800, MOD = 1e9 + 7;

vector<array<int, 3>> d;
int n, S, T;

struct DSU{
    int par[MAX];
    void init(){
        memset(par, -1, sizeof(par));
    }
    int get(int u){
        if(par[u] < 0) return u;
        return get(par[u]);
    }
    stack<array<int, 4>> st;
    void unite(int u, int v, bool b){
        u = get(u), v = get(v);
        if(u == v) return;
        if(-par[u] < -par[v]) swap(u, v);
        if(b) st.push({u, v, par[u], par[v]});
        par[u] += par[v];
        par[v] = u;
    }
    bool same(int u, int v){
        return get(u) == get(v);
    }
    void roll_back(){
        auto a = st.top();
        st.pop();
        par[a[0]] = a[2];
        par[a[1]] = a[3];
    }
};

DSU dsu;

vector<int> g[MAX];
int in[MAX], out[MAX], par[LOGMAX][MAX], H[MAX];
int t = 0;
void dfs(int node, int p, int h){
    H[node] = h;
    in[node] = ++t;
    for(int to : g[node]){
        if(to == p) continue;
        dfs(to, node, h + 1);
    }
    out[node] = t;
}

bool isA(int u, int v){
    return in[u] <= in[v] && out[u] >= out[v];
}
int dist(int u, int v){
    int l = u;
    if(isA(u, v)) return H[v] - H[u];
    if(isA(v, u)) return H[u] - H[v];
    for(int j = LOGMAX - 1; j >= 0; j--){
        if(!isA(par[j][l], v)) l = par[j][l];
    }
    l = par[0][l];
    return H[u] + H[v] - 2 * H[l];
}

void solve(){
    cin >> n >> S >> T;
    dsu.init();
    for(int i = 1; i < n; i++){
        int u, v, w; cin >> u >> v >> w;
        if(w) d.push_back({u, v, w});
        else dsu.unite(u, v, 0);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 1, 0);
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 1; i <= n; i++){
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
    int k = d.size();
    int ans = oo;
    sort(all(d));
    do{
        int cur = S;
        int D = 0;
        bool b = 1;
        for(auto a : d){
            if(dsu.same(cur, T)){
                D += dist(cur, T);
                break;
            }
            if(!dsu.same(cur, a[2])){
                b = 0;
                break;
            }
            D += dist(cur, a[2]);
            cur = a[2];
            if(dsu.same(cur, a[1])){
                D += dist(cur, a[1]);
                dsu.unite(a[0], a[1], 1);
                cur = a[1];
            }
            else if(dsu.same(cur, a[0])){
                D += dist(cur, a[0]);
                dsu.unite(a[0], a[1], 1);
                cur = a[0];
            }
            else{
                b = 0;
                break;
            }
        }
        while(dsu.st.size()) dsu.roll_back();
        if(!b) continue;
        ans = min(ans, D);
    }
    while(next_permutation(all(d)));
    cout << ans + 1 << '\n';
}   

signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    int t = 1;
    while(t--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:88:9: warning: unused variable 'k' [-Wunused-variable]
   88 |     int k = d.size();
      |         ^

• Subtask 1: 0 / 23
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41