oj.uz

Submission #999292

# Submission time Handle Problem Language Result Execution time Memory
999292 2024-06-15T09:18:51 Z vjudge1 LOSTIKS (INOI20_lostiks) C++17
23 / 100
 2000 ms 29940 KB 
#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 = 1e5 + 5, LOGMAX = 20, B = 800, MOD = 1e9 + 7;

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

int org[MAX];
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<int> 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);
            st.push(v);
        }
        par[u] += par[v];
        par[v] = u;
    }
    bool same(int u, int v){
        return get(u) == get(v);
    }
    void roll_back(){
        while(st.size()){
            auto a = st.top();
            st.pop();
            par[a] = org[a];
        }
    }
};
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;
    par[0][node] = p;
    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);
    }
    for(int i = 0; i < MAX; i++){
        org[i] = dsu.par[i];
    }
    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)) 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;
            }
        }
        D += dist(cur, T); 
        dsu.roll_back();
        if(!b) continue;
        ans = min(ans, D);
    }
    while(next_permutation(all(d)));
    if(ans >= oo) cout << "-1\n";
    else cout << ans << '\n';
}   

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

Compilation message

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

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22108 KB Output is correct
2 Correct 2 ms 22108 KB Output is correct
3 Correct 57 ms 26144 KB Output is correct
4 Correct 57 ms 26152 KB Output is correct
5 Correct 59 ms 26196 KB Output is correct
6 Correct 57 ms 26152 KB Output is correct
7 Correct 56 ms 26192 KB Output is correct
8 Correct 56 ms 26192 KB Output is correct
9 Correct 65 ms 26108 KB Output is correct
10 Correct 57 ms 26192 KB Output is correct
11 Correct 57 ms 26180 KB Output is correct
12 Correct 55 ms 26452 KB Output is correct
13 Correct 56 ms 27332 KB Output is correct
14 Correct 54 ms 26332 KB Output is correct
15 Correct 59 ms 26704 KB Output is correct
16 Correct 58 ms 27476 KB Output is correct
17 Correct 56 ms 26964 KB Output is correct
18 Correct 56 ms 26960 KB Output is correct
19 Correct 57 ms 29776 KB Output is correct
20 Correct 61 ms 28496 KB Output is correct
21 Correct 61 ms 29940 KB Output is correct
22 Correct 3 ms 22108 KB Output is correct
23 Correct 3 ms 22108 KB Output is correct
24 Correct 3 ms 22108 KB Output is correct
25 Correct 6 ms 22108 KB Output is correct
26 Correct 3 ms 22108 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22104 KB Output is correct
2 Correct 3 ms 22108 KB Output is correct
3 Correct 357 ms 22108 KB Output is correct
4 Correct 387 ms 22160 KB Output is correct
5 Execution timed out 2055 ms 22364 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22108 KB Output is correct
2 Correct 2 ms 22108 KB Output is correct
3 Correct 57 ms 26144 KB Output is correct
4 Correct 57 ms 26152 KB Output is correct
5 Correct 59 ms 26196 KB Output is correct
6 Correct 57 ms 26152 KB Output is correct
7 Correct 56 ms 26192 KB Output is correct
8 Correct 56 ms 26192 KB Output is correct
9 Correct 65 ms 26108 KB Output is correct
10 Correct 57 ms 26192 KB Output is correct
11 Correct 57 ms 26180 KB Output is correct
12 Correct 55 ms 26452 KB Output is correct
13 Correct 56 ms 27332 KB Output is correct
14 Correct 54 ms 26332 KB Output is correct
15 Correct 59 ms 26704 KB Output is correct
16 Correct 58 ms 27476 KB Output is correct
17 Correct 56 ms 26964 KB Output is correct
18 Correct 56 ms 26960 KB Output is correct
19 Correct 57 ms 29776 KB Output is correct
20 Correct 61 ms 28496 KB Output is correct
21 Correct 61 ms 29940 KB Output is correct
22 Correct 3 ms 22108 KB Output is correct
23 Correct 3 ms 22108 KB Output is correct
24 Correct 3 ms 22108 KB Output is correct
25 Correct 6 ms 22108 KB Output is correct
26 Correct 3 ms 22108 KB Output is correct
27 Correct 3 ms 22104 KB Output is correct
28 Correct 3 ms 22108 KB Output is correct
29 Correct 357 ms 22108 KB Output is correct
30 Correct 387 ms 22160 KB Output is correct
31 Execution timed out 2055 ms 22364 KB Time limit exceeded
32 Halted 0 ms 0 KB -