oj.uz

Submission #635365

# Submission time Handle Problem Language Result Execution time Memory
635365 2022-08-26T07:02:07 Z MohammadAghil LOSTIKS (INOI20_lostiks) C++17
36 / 100
 436 ms 110072 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(1e9) + 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);
    }
}

int 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]]);
                    }
                }
            }
        }
    }
    int 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]]);
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 84 ms 31308 KB Output is correct
4 Correct 77 ms 31228 KB Output is correct
5 Correct 82 ms 31308 KB Output is correct
6 Correct 74 ms 31216 KB Output is correct
7 Correct 89 ms 31380 KB Output is correct
8 Correct 104 ms 31356 KB Output is correct
9 Correct 99 ms 31572 KB Output is correct
10 Correct 79 ms 31360 KB Output is correct
11 Correct 78 ms 31380 KB Output is correct
12 Correct 88 ms 32724 KB Output is correct
13 Correct 68 ms 33056 KB Output is correct
14 Correct 73 ms 32692 KB Output is correct
15 Incorrect 72 ms 32912 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 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 177 ms 67808 KB Output is correct
6 Correct 149 ms 67904 KB Output is correct
7 Correct 191 ms 67884 KB Output is correct
8 Correct 160 ms 67848 KB Output is correct
9 Correct 172 ms 67868 KB Output is correct
10 Correct 85 ms 67848 KB Output is correct
11 Correct 83 ms 67788 KB Output is correct
12 Correct 84 ms 67796 KB Output is correct
13 Correct 84 ms 67820 KB Output is correct
14 Correct 85 ms 67916 KB Output is correct
15 Correct 150 ms 67972 KB Output is correct
16 Correct 196 ms 67908 KB Output is correct
17 Correct 163 ms 67876 KB Output is correct
18 Correct 87 ms 68052 KB Output is correct
19 Correct 82 ms 67932 KB Output is correct
20 Correct 86 ms 67944 KB Output is correct
21 Correct 83 ms 68016 KB Output is correct
22 Correct 84 ms 68300 KB Output is correct
23 Correct 84 ms 68480 KB Output is correct
24 Correct 81 ms 68356 KB Output is correct
25 Correct 436 ms 110072 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 84 ms 31308 KB Output is correct
4 Correct 77 ms 31228 KB Output is correct
5 Correct 82 ms 31308 KB Output is correct
6 Correct 74 ms 31216 KB Output is correct
7 Correct 89 ms 31380 KB Output is correct
8 Correct 104 ms 31356 KB Output is correct
9 Correct 99 ms 31572 KB Output is correct
10 Correct 79 ms 31360 KB Output is correct
11 Correct 78 ms 31380 KB Output is correct
12 Correct 88 ms 32724 KB Output is correct
13 Correct 68 ms 33056 KB Output is correct
14 Correct 73 ms 32692 KB Output is correct
15 Incorrect 72 ms 32912 KB Output isn't correct
16 Halted 0 ms 0 KB -