oj.uz

Submission #635367

# Submission time Handle Problem Language Result Execution time Memory
635367 2022-08-26T07:03:44 Z MohammadAghil LOSTIKS (INOI20_lostiks) C++17
36 / 100
 467 ms 196216 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]]);
    }
    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 89 ms 31320 KB Output is correct
4 Correct 117 ms 31308 KB Output is correct
5 Correct 79 ms 31400 KB Output is correct
6 Correct 92 ms 31436 KB Output is correct
7 Correct 90 ms 31328 KB Output is correct
8 Correct 93 ms 31404 KB Output is correct
9 Correct 81 ms 31604 KB Output is correct
10 Correct 106 ms 31404 KB Output is correct
11 Correct 93 ms 31344 KB Output is correct
12 Correct 67 ms 32792 KB Output is correct
13 Correct 78 ms 32996 KB Output is correct
14 Correct 74 ms 32752 KB Output is correct
15 Incorrect 66 ms 32908 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 24036 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 191 ms 110984 KB Output is correct
6 Correct 172 ms 111032 KB Output is correct
7 Correct 200 ms 111036 KB Output is correct
8 Correct 184 ms 110968 KB Output is correct
9 Correct 189 ms 110952 KB Output is correct
10 Correct 106 ms 110984 KB Output is correct
11 Correct 107 ms 110980 KB Output is correct
12 Correct 111 ms 110924 KB Output is correct
13 Correct 108 ms 110932 KB Output is correct
14 Correct 110 ms 110888 KB Output is correct
15 Correct 166 ms 110908 KB Output is correct
16 Correct 212 ms 111040 KB Output is correct
17 Correct 185 ms 111008 KB Output is correct
18 Correct 114 ms 111052 KB Output is correct
19 Correct 109 ms 111116 KB Output is correct
20 Correct 104 ms 111080 KB Output is correct
21 Correct 103 ms 111144 KB Output is correct
22 Correct 109 ms 111588 KB Output is correct
23 Correct 110 ms 111436 KB Output is correct
24 Correct 117 ms 111472 KB Output is correct
25 Correct 467 ms 196216 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 89 ms 31320 KB Output is correct
4 Correct 117 ms 31308 KB Output is correct
5 Correct 79 ms 31400 KB Output is correct
6 Correct 92 ms 31436 KB Output is correct
7 Correct 90 ms 31328 KB Output is correct
8 Correct 93 ms 31404 KB Output is correct
9 Correct 81 ms 31604 KB Output is correct
10 Correct 106 ms 31404 KB Output is correct
11 Correct 93 ms 31344 KB Output is correct
12 Correct 67 ms 32792 KB Output is correct
13 Correct 78 ms 32996 KB Output is correct
14 Correct 74 ms 32752 KB Output is correct
15 Incorrect 66 ms 32908 KB Output isn't correct
16 Halted 0 ms 0 KB -