oj.uz

Submission #635368

# Submission time Handle Problem Language Result Execution time Memory
635368 2022-08-26T07:06:12 Z MohammadAghil LOSTIKS (INOI20_lostiks) C++17
36 / 100
 478 ms 196424 KB 
#include <bits/stdc++.h>
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

void dbg(){
    cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
    cerr << " " << h << ",";
    dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)

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 = 21, inf = ll(1e18) + 5;

int val[maxn], ed[maxm], nxt[maxm], tmp;
vector<pp> adj[maxn];

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

int dist[maxm + 5][maxn];

void dfs2(int r, int p, int id){
    for(auto[c, w]: adj[r]) if(c - p){
        dist[id][c] = dist[id][r] + 1;
        dfs2(c, r, id);
    }
}

ll dp[1<<maxm][maxm];

int main(){ IOS();
    int n, 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, -1, 0);
    rep(i,0,m){
        dfs2(ed[i], -1, i);
    }
    assert(tmp == m && m < 21);
    dfs2(s, -1, m);
    auto chk = [&](int msk, int r){
        return (val[r]&msk) == val[r];
    };
    per(i,(1<<m)-1,1){
        rep(e,0,m){
            dp[i][e] = inf;
            int r = ed[e];
            if((i>>e&1) && chk(i, r)){
                if(chk(i, t)){
                    dp[i][e] = dist[e][t];
                }else{
                    rep(x,0,m) if(!(i>>x&1) && chk(i, nxt[x]) && chk(i, ed[x])){
                        dp[i][e] = min(dp[i][e], dp[i^(1<<x)][x] + dist[e][nxt[x]] + dist[x][nxt[x]]);
                    }
                }
            }
        }
    }
    ll ans = inf;
    rep(i,0,m){
        if(chk(0, nxt[i]) && chk(0, ed[i])) ans = min(ans, dp[1<<i][i] + dist[m][nxt[i]] + dist[i][nxt[i]]);
    }
    if(chk(0, t)){
        ans = dist[m][t];
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 73 ms 31220 KB Output is correct
4 Correct 94 ms 31240 KB Output is correct
5 Correct 90 ms 31348 KB Output is correct
6 Correct 80 ms 31228 KB Output is correct
7 Correct 73 ms 31428 KB Output is correct
8 Correct 71 ms 31308 KB Output is correct
9 Correct 77 ms 31596 KB Output is correct
10 Correct 73 ms 31412 KB Output is correct
11 Correct 77 ms 31308 KB Output is correct
12 Correct 69 ms 32768 KB Output is correct
13 Correct 68 ms 33140 KB Output is correct
14 Correct 63 ms 32684 KB Output is correct
15 Incorrect 67 ms 32948 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23776 KB Output is correct
3 Correct 12 ms 24064 KB Output is correct
4 Correct 12 ms 24048 KB Output is correct
5 Correct 215 ms 111064 KB Output is correct
6 Correct 161 ms 110920 KB Output is correct
7 Correct 208 ms 110948 KB Output is correct
8 Correct 185 ms 110916 KB Output is correct
9 Correct 194 ms 110924 KB Output is correct
10 Correct 109 ms 110900 KB Output is correct
11 Correct 104 ms 111004 KB Output is correct
12 Correct 102 ms 110924 KB Output is correct
13 Correct 104 ms 111072 KB Output is correct
14 Correct 106 ms 110928 KB Output is correct
15 Correct 171 ms 111012 KB Output is correct
16 Correct 216 ms 111000 KB Output is correct
17 Correct 191 ms 111044 KB Output is correct
18 Correct 107 ms 111076 KB Output is correct
19 Correct 109 ms 111116 KB Output is correct
20 Correct 106 ms 111140 KB Output is correct
21 Correct 104 ms 111180 KB Output is correct
22 Correct 105 ms 111444 KB Output is correct
23 Correct 109 ms 111444 KB Output is correct
24 Correct 104 ms 111456 KB Output is correct
25 Correct 478 ms 196424 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 73 ms 31220 KB Output is correct
4 Correct 94 ms 31240 KB Output is correct
5 Correct 90 ms 31348 KB Output is correct
6 Correct 80 ms 31228 KB Output is correct
7 Correct 73 ms 31428 KB Output is correct
8 Correct 71 ms 31308 KB Output is correct
9 Correct 77 ms 31596 KB Output is correct
10 Correct 73 ms 31412 KB Output is correct
11 Correct 77 ms 31308 KB Output is correct
12 Correct 69 ms 32768 KB Output is correct
13 Correct 68 ms 33140 KB Output is correct
14 Correct 63 ms 32684 KB Output is correct
15 Incorrect 67 ms 32948 KB Output isn't correct
16 Halted 0 ms 0 KB -