oj.uz

Submission #635750

# Submission time Handle Problem Language Result Execution time Memory
635750 2022-08-26T18:32:50 Z MohammadAghil LOSTIKS (INOI20_lostiks) C++17
100 / 100
 1399 ms 184876 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define ff first
#define ss second


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
//    #ifndef ONLINE_JUDGE
//        freopen("inp.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
//    #endif
}

const ll mod = 1e9 + 7, maxn = 1e6 + 5, maxm = 20, lg = 20, inf = ll(1e9) + 5;

int val[maxn], ed[maxm], nxt[maxm], tmp, n;
vector<pp> adj[maxn];
int dq[maxn], st, en, tmp_vl[maxm][maxm];

int par[maxn][lg], h[maxn];

void dfs(int r){

    rep(i,0,lg) par[r][i] = r;
    dq[st = 0] = r, en = 1;
    while(st < en){
        int r = dq[st++];
        rep(i,1,lg) par[r][i] = par[par[r][i-1]][i-1];
        for(auto&[c, w]: adj[r]) if(c - par[r][0]){
            val[c] = val[r];
            h[c] = h[r] + 1;
            par[c][0] = r;
            if(w + 1){
                ed[tmp] = r;
                nxt[tmp] = w;
                val[c] |= 1<<tmp;
                tmp++;
            }
            dq[en++] = c;
        }
    }


//    val[r] |= val[p];
//    for(auto&[c, w]: adj[r]) if(c - p){
//        if(w + 1){
//            ed[tmp] = r;
//            nxt[tmp] = w;
//            val[c] = 1<<tmp;
//            tmp++;
//            dfs(c, r);
//        } else{
//            dfs(c, r);
//        }
//    }
}


//void dfs2(int r, int id){
////    vector<pp> stk;
////    for(auto&[c, w]: adj[r]) if(c - p){
////        dist[id][c] = dist[id][r] + 1;
////        dfs2(c, r);
////    }
//    dq[st = 0]  = r, en = 1;
//    fill(dist[id], dist[id] + n, -1);
//    dist[id][r] = 0;
//    while(st < en){
//        int r = dq[st++];
//        for(auto&[c, w]: adj[r]) if(dist[id][c] == -1){
//            dist[id][c] = dist[id][r] + 1;
//            dq[en++] = c;
//        }
//    }
//}

int lca(int u, int v){
    if(h[u] > h[v]) swap(u, v);
    per(i,lg-1,0) if(h[par[v][i]] >= h[u]) v = par[v][i];
    if(u == v) return u;
    per(i,lg-1,0) if(par[u][i] - par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
}

int dist(int u, int v){
    return h[u] + h[v] - (h[lca(u, v)]<<1);
}

int dp[maxm][1<<maxm];

int main(){ IOS();
    // tof to zatet ba in limitaie soal
    int s, t; cin >> n >> s >> t; s--, t--;
    int m = 0;
    rep(i,1,n){
        int u, v, w; cin >> u >> v >> w; u--, v--, w--;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        m += w != -1;
    }
    dfs(s);
//    rep(i,0,m){
//        dfs2(ed[i], i);
//    }
//    dfs2(s, m);

    rep(i,0,m){
        rep(j,0,m){
            tmp_vl[i][j] = dist(ed[i], nxt[j]) + dist(ed[j], nxt[j]);
        }
    }

    auto chk = [&](int msk, int r){
        return (val[r]&msk) == val[r];
    };
    vector<int> is(m), nis(m);
    int ptr_is = 0, ptr_nis = 0;
    per(i,(1<<m)-1,1){
        ptr_is = ptr_nis = 0;
        rep(e,0,m) {
            if(i>>e&1){
                if(chk(i, ed[e])) is[ptr_is++] = e;
            }else{
                if(chk(i, nxt[e]) && chk(i, ed[e])) nis[ptr_nis++] = e;
            }
        }
        rep(x,0,ptr_is){
            int e = is[x];
            dp[e][i] = inf;
            if(chk(i, t)){
                dp[e][i] = dist(ed[e], t);
            }else{
                rep(j,0,ptr_nis){
                    dp[e][i] = min(dp[e][i], dp[nis[j]][i^(1<<nis[j])] + tmp_vl[e][nis[j]]);
                }
            }
        }
    }
    int ans = inf;
    rep(i,0,m){
        if(chk(0, nxt[i]) && chk(0, ed[i])) ans = min(ans, dp[i][1<<i] + dist(s, nxt[i]) + dist(ed[i], nxt[i]));
    }
    if(chk(0, t)){
        ans = dist(s, t);
    }
    cout << (ans == inf? -1: ans) << '\n';
    return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23824 KB Output is correct
3 Correct 67 ms 36600 KB Output is correct
4 Correct 87 ms 36604 KB Output is correct
5 Correct 87 ms 36576 KB Output is correct
6 Correct 68 ms 36636 KB Output is correct
7 Correct 66 ms 36548 KB Output is correct
8 Correct 66 ms 36520 KB Output is correct
9 Correct 66 ms 36540 KB Output is correct
10 Correct 73 ms 36628 KB Output is correct
11 Correct 67 ms 36568 KB Output is correct
12 Correct 75 ms 36020 KB Output is correct
13 Correct 75 ms 35968 KB Output is correct
14 Correct 84 ms 35928 KB Output is correct
15 Correct 79 ms 36020 KB Output is correct
16 Correct 72 ms 35960 KB Output is correct
17 Correct 73 ms 35960 KB Output is correct
18 Correct 74 ms 35964 KB Output is correct
19 Correct 74 ms 35916 KB Output is correct
20 Correct 80 ms 35936 KB Output is correct
21 Correct 80 ms 35916 KB Output is correct
22 Correct 12 ms 23880 KB Output is correct
23 Correct 12 ms 23796 KB Output is correct
24 Correct 12 ms 23892 KB Output is correct
25 Correct 12 ms 23892 KB Output is correct
26 Correct 13 ms 23924 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23840 KB Output is correct
3 Correct 13 ms 23980 KB Output is correct
4 Correct 14 ms 23860 KB Output is correct
5 Correct 186 ms 55068 KB Output is correct
6 Correct 99 ms 53548 KB Output is correct
7 Correct 195 ms 54976 KB Output is correct
8 Correct 155 ms 55088 KB Output is correct
9 Correct 134 ms 54264 KB Output is correct
10 Correct 64 ms 47336 KB Output is correct
11 Correct 69 ms 47364 KB Output is correct
12 Correct 64 ms 47304 KB Output is correct
13 Correct 63 ms 47296 KB Output is correct
14 Correct 63 ms 47308 KB Output is correct
15 Correct 144 ms 54220 KB Output is correct
16 Correct 181 ms 54732 KB Output is correct
17 Correct 155 ms 56096 KB Output is correct
18 Correct 66 ms 47300 KB Output is correct
19 Correct 62 ms 47308 KB Output is correct
20 Correct 64 ms 47344 KB Output is correct
21 Correct 61 ms 47316 KB Output is correct
22 Correct 72 ms 47308 KB Output is correct
23 Correct 65 ms 47376 KB Output is correct
24 Correct 60 ms 47308 KB Output is correct
25 Correct 765 ms 89440 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23824 KB Output is correct
3 Correct 67 ms 36600 KB Output is correct
4 Correct 87 ms 36604 KB Output is correct
5 Correct 87 ms 36576 KB Output is correct
6 Correct 68 ms 36636 KB Output is correct
7 Correct 66 ms 36548 KB Output is correct
8 Correct 66 ms 36520 KB Output is correct
9 Correct 66 ms 36540 KB Output is correct
10 Correct 73 ms 36628 KB Output is correct
11 Correct 67 ms 36568 KB Output is correct
12 Correct 75 ms 36020 KB Output is correct
13 Correct 75 ms 35968 KB Output is correct
14 Correct 84 ms 35928 KB Output is correct
15 Correct 79 ms 36020 KB Output is correct
16 Correct 72 ms 35960 KB Output is correct
17 Correct 73 ms 35960 KB Output is correct
18 Correct 74 ms 35964 KB Output is correct
19 Correct 74 ms 35916 KB Output is correct
20 Correct 80 ms 35936 KB Output is correct
21 Correct 80 ms 35916 KB Output is correct
22 Correct 12 ms 23880 KB Output is correct
23 Correct 12 ms 23796 KB Output is correct
24 Correct 12 ms 23892 KB Output is correct
25 Correct 12 ms 23892 KB Output is correct
26 Correct 13 ms 23924 KB Output is correct
27 Correct 12 ms 23764 KB Output is correct
28 Correct 12 ms 23840 KB Output is correct
29 Correct 13 ms 23980 KB Output is correct
30 Correct 14 ms 23860 KB Output is correct
31 Correct 186 ms 55068 KB Output is correct
32 Correct 99 ms 53548 KB Output is correct
33 Correct 195 ms 54976 KB Output is correct
34 Correct 155 ms 55088 KB Output is correct
35 Correct 134 ms 54264 KB Output is correct
36 Correct 64 ms 47336 KB Output is correct
37 Correct 69 ms 47364 KB Output is correct
38 Correct 64 ms 47304 KB Output is correct
39 Correct 63 ms 47296 KB Output is correct
40 Correct 63 ms 47308 KB Output is correct
41 Correct 144 ms 54220 KB Output is correct
42 Correct 181 ms 54732 KB Output is correct
43 Correct 155 ms 56096 KB Output is correct
44 Correct 66 ms 47300 KB Output is correct
45 Correct 62 ms 47308 KB Output is correct
46 Correct 64 ms 47344 KB Output is correct
47 Correct 61 ms 47316 KB Output is correct
48 Correct 72 ms 47308 KB Output is correct
49 Correct 65 ms 47376 KB Output is correct
50 Correct 60 ms 47308 KB Output is correct
51 Correct 765 ms 89440 KB Output is correct
52 Correct 1056 ms 151400 KB Output is correct
53 Correct 1028 ms 151440 KB Output is correct
54 Correct 1029 ms 154388 KB Output is correct
55 Correct 1111 ms 154076 KB Output is correct
56 Correct 1041 ms 154216 KB Output is correct
57 Correct 1032 ms 154256 KB Output is correct
58 Correct 13 ms 23892 KB Output is correct
59 Correct 15 ms 23808 KB Output is correct
60 Correct 12 ms 23820 KB Output is correct
61 Correct 1039 ms 154204 KB Output is correct
62 Correct 1066 ms 161420 KB Output is correct
63 Correct 1018 ms 157772 KB Output is correct
64 Correct 89 ms 37936 KB Output is correct
65 Correct 79 ms 37644 KB Output is correct
66 Correct 1033 ms 154160 KB Output is correct
67 Correct 1041 ms 154208 KB Output is correct
68 Correct 1063 ms 183588 KB Output is correct
69 Correct 1028 ms 183556 KB Output is correct
70 Correct 1094 ms 184876 KB Output is correct
71 Correct 1336 ms 184108 KB Output is correct
72 Correct 1091 ms 184232 KB Output is correct
73 Correct 937 ms 176732 KB Output is correct
74 Correct 955 ms 176612 KB Output is correct
75 Correct 915 ms 176684 KB Output is correct
76 Correct 915 ms 176580 KB Output is correct
77 Correct 927 ms 176496 KB Output is correct
78 Correct 1399 ms 178172 KB Output is correct
79 Correct 1234 ms 178092 KB Output is correct
80 Correct 1136 ms 175784 KB Output is correct
81 Correct 1064 ms 170232 KB Output is correct
82 Correct 1055 ms 170156 KB Output is correct
83 Correct 1057 ms 170176 KB Output is correct
84 Correct 1137 ms 170128 KB Output is correct
85 Correct 1142 ms 170148 KB Output is correct
86 Correct 1146 ms 170064 KB Output is correct
87 Correct 1111 ms 170208 KB Output is correct