oj.uz

Submission #999293

# Submission time Handle Problem Language Result Execution time Memory
999293 2024-06-15T09:20:04 Z vjudge1 LOSTIKS (INOI20_lostiks) C++17
23 / 100
 2000 ms 104600 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 = 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;
    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);
    }
    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); 
        while(dsu.st.size()) dsu.roll_back();
        if(!b) continue;
        ans = min(ans, D);
    }
    while(next_permutation(all(d)));
    if(ans >= oo) ans = -1;
    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:89:9: warning: unused variable 'k' [-Wunused-variable]
   89 |     int k = d.size();
      |         ^

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 78172 KB Output is correct
2 Correct 9 ms 78172 KB Output is correct
3 Correct 72 ms 100432 KB Output is correct
4 Correct 75 ms 100692 KB Output is correct
5 Correct 71 ms 100688 KB Output is correct
6 Correct 71 ms 100688 KB Output is correct
7 Correct 71 ms 100712 KB Output is correct
8 Correct 72 ms 100692 KB Output is correct
9 Correct 74 ms 100692 KB Output is correct
10 Correct 69 ms 100512 KB Output is correct
11 Correct 79 ms 100696 KB Output is correct
12 Correct 73 ms 100792 KB Output is correct
13 Correct 68 ms 101884 KB Output is correct
14 Correct 75 ms 100948 KB Output is correct
15 Correct 70 ms 101204 KB Output is correct
16 Correct 69 ms 101768 KB Output is correct
17 Correct 67 ms 101712 KB Output is correct
18 Correct 67 ms 101456 KB Output is correct
19 Correct 88 ms 104528 KB Output is correct
20 Correct 72 ms 102992 KB Output is correct
21 Correct 71 ms 104600 KB Output is correct
22 Correct 10 ms 78168 KB Output is correct
23 Correct 10 ms 78172 KB Output is correct
24 Correct 10 ms 78168 KB Output is correct
25 Correct 13 ms 78196 KB Output is correct
26 Correct 10 ms 78172 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 78172 KB Output is correct
2 Correct 9 ms 78184 KB Output is correct
3 Correct 349 ms 78040 KB Output is correct
4 Correct 457 ms 78168 KB Output is correct
5 Execution timed out 2009 ms 80472 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 78172 KB Output is correct
2 Correct 9 ms 78172 KB Output is correct
3 Correct 72 ms 100432 KB Output is correct
4 Correct 75 ms 100692 KB Output is correct
5 Correct 71 ms 100688 KB Output is correct
6 Correct 71 ms 100688 KB Output is correct
7 Correct 71 ms 100712 KB Output is correct
8 Correct 72 ms 100692 KB Output is correct
9 Correct 74 ms 100692 KB Output is correct
10 Correct 69 ms 100512 KB Output is correct
11 Correct 79 ms 100696 KB Output is correct
12 Correct 73 ms 100792 KB Output is correct
13 Correct 68 ms 101884 KB Output is correct
14 Correct 75 ms 100948 KB Output is correct
15 Correct 70 ms 101204 KB Output is correct
16 Correct 69 ms 101768 KB Output is correct
17 Correct 67 ms 101712 KB Output is correct
18 Correct 67 ms 101456 KB Output is correct
19 Correct 88 ms 104528 KB Output is correct
20 Correct 72 ms 102992 KB Output is correct
21 Correct 71 ms 104600 KB Output is correct
22 Correct 10 ms 78168 KB Output is correct
23 Correct 10 ms 78172 KB Output is correct
24 Correct 10 ms 78168 KB Output is correct
25 Correct 13 ms 78196 KB Output is correct
26 Correct 10 ms 78172 KB Output is correct
27 Correct 9 ms 78172 KB Output is correct
28 Correct 9 ms 78184 KB Output is correct
29 Correct 349 ms 78040 KB Output is correct
30 Correct 457 ms 78168 KB Output is correct
31 Execution timed out 2009 ms 80472 KB Time limit exceeded
32 Halted 0 ms 0 KB -