oj.uz

Submission #635364

# Submission time Handle Problem Language Result Execution time Memory
635364 2022-08-26T07:00:04 Z MohammadAghil LOSTIKS (INOI20_lostiks) C++17
36 / 100
 421 ms 106092 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 = 20, 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);
        er(ed[i], nxt[i]);
    }
    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 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 119 ms 31604 KB Output is correct
4 Correct 110 ms 31640 KB Output is correct
5 Correct 82 ms 31752 KB Output is correct
6 Correct 81 ms 31628 KB Output is correct
7 Correct 85 ms 31740 KB Output is correct
8 Correct 88 ms 31804 KB Output is correct
9 Correct 95 ms 32028 KB Output is correct
10 Correct 85 ms 31748 KB Output is correct
11 Correct 94 ms 31692 KB Output is correct
12 Correct 72 ms 33212 KB Output is correct
13 Correct 73 ms 33548 KB Output is correct
14 Correct 82 ms 33124 KB Output is correct
15 Incorrect 84 ms 33256 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 12 ms 23872 KB Output is correct
3 Correct 13 ms 24020 KB Output is correct
4 Correct 13 ms 24020 KB Output is correct
5 Correct 160 ms 65976 KB Output is correct
6 Correct 126 ms 65844 KB Output is correct
7 Correct 184 ms 65880 KB Output is correct
8 Correct 157 ms 65820 KB Output is correct
9 Correct 172 ms 65896 KB Output is correct
10 Correct 79 ms 65844 KB Output is correct
11 Correct 76 ms 65972 KB Output is correct
12 Correct 77 ms 65916 KB Output is correct
13 Correct 77 ms 65964 KB Output is correct
14 Correct 83 ms 65908 KB Output is correct
15 Correct 143 ms 65848 KB Output is correct
16 Correct 183 ms 65916 KB Output is correct
17 Correct 149 ms 65892 KB Output is correct
18 Correct 80 ms 66140 KB Output is correct
19 Correct 82 ms 66060 KB Output is correct
20 Correct 83 ms 66028 KB Output is correct
21 Correct 79 ms 66120 KB Output is correct
22 Correct 81 ms 66424 KB Output is correct
23 Correct 80 ms 66380 KB Output is correct
24 Correct 78 ms 66380 KB Output is correct
25 Correct 421 ms 106092 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 11 ms 23764 KB Output is correct
3 Correct 119 ms 31604 KB Output is correct
4 Correct 110 ms 31640 KB Output is correct
5 Correct 82 ms 31752 KB Output is correct
6 Correct 81 ms 31628 KB Output is correct
7 Correct 85 ms 31740 KB Output is correct
8 Correct 88 ms 31804 KB Output is correct
9 Correct 95 ms 32028 KB Output is correct
10 Correct 85 ms 31748 KB Output is correct
11 Correct 94 ms 31692 KB Output is correct
12 Correct 72 ms 33212 KB Output is correct
13 Correct 73 ms 33548 KB Output is correct
14 Correct 82 ms 33124 KB Output is correct
15 Incorrect 84 ms 33256 KB Output isn't correct
16 Halted 0 ms 0 KB -