oj.uz

Submission #470274

# Submission time Handle Problem Language Result Execution time Memory
470274 2021-09-03T11:10:34 Z radal LOSTIKS (INOI20_lostiks) C++14
23 / 100
 653 ms 918904 KB 
#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define pb push_back
#define debug(x) cerr << #x <<  " : " << x << endl;
#define X first
#define Y second
using namespace std;

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

const ll N = 1e5+20,mod = 1e9+7,maxm = (1 << 9),inf = 1e18;
int poww(int a,int k){
    if (!k) return 1;
    if (k == 1) return a;
    int r = poww(a,k/2);
    return 1ll*r*r%mod*poww(a,k&1)%mod;
}
int n,s,t;
vector<pll> adj[N];
int k[22],par[N][20],h[N],mark[N],din2[N],din3[N],din4[N];
vector<int> dp[N][22],out[22],in[22];
ll cost[maxm][N];
pll e[22];
int cnt;
bitset<N> vis;
void bfs(int v){
    queue<int> q;
    q.push(k[v]);
    vis[k[v]] = 1;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (pll w : adj[u]){
            if (vis[w.X]) continue;
            vis[w.X] = 1;
            q.push(w.X);
            for (int x : dp[u][v])
                dp[w.X][v].pb(x);
            if (w.Y)
                dp[w.X][v].pb(w.Y);
            if (u == t && v != cnt+1) dp[w.X][v].pb(cnt+1);
        }
    }
    vis.reset();
}
bool pre(int v){
    mark[v] = 1;
    for (int u : dp[s][v]){
        out[u].pb(v);
        in[v].pb(u);
        if (mark[u] == 1)
            return 0;
        if (mark[u] == 2) continue;
        if (!pre(u)) return 0;
    }
    for(int u : dp[e[v].X][v]){
        if (u != v){
            out[u].pb(v);
            in[v].pb(u);
            if (mark[u] == 1) return 0;
            if (!mark[u] && !pre(u)) return 0;
        }
    }
    for(int u : dp[e[v].Y][v]){
        if (u != v){
            out[u].pb(v);
            in[v].pb(u);
            if (mark[u] == 1) return 0;
            if (!mark[u] && !pre(u)) return 0;
        }
    }
    mark[v] = 2;
    return 1;
}
void dfs(int v,int p){
    for (pll u : adj[v]){
        if (u.X == p) continue;
        h[u.X] = h[v]+1;
        par[u.X][0] = v;
        dfs(u.X,v);
    }
}
inline int lca(int u,int v){
    if (h[u] > h[v]) swap(u,v);
    repr(i,18,0)
        if (h[v]-h[u] >= (1 << i))
            v = par[v][i];
    if (u == v) return u;
    repr(i,18,0){
        if (par[v][i] != par[u][i]){
            v = par[v][i];
            u = par[u][i];
        }
    }
    return par[v][0];
}
inline int dist(int u,int v){
    int w = lca(u,v);
    return h[v]+h[u]-2*h[w];
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(cost,63,sizeof cost);
    cin >> n >> s >> t;
    rep(i,1,n){
        int u,v,w;
        cin >> u >> v >> w;
        if (!w){
            adj[u].pb({v,0});
            adj[v].pb({u,0});
        }
        else{
            cnt++;
            k[cnt] = w;
            e[cnt] = {u,v};
            adj[u].pb({v,cnt});
            adj[v].pb({u,cnt});
        }
    }
    k[cnt+1] = t;
    rep(i,1,cnt+2) bfs(i);
    e[cnt+1] = {t,t};
    if (!pre(cnt+1)){
        cout << -1;
        return 0;
    }
    dfs(1,-1);
    rep(j,1,19){
        rep(i,2,n+1){
            if (h[i] < (1 << j)) continue;
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
    rep(i,1,cnt+1) if(dist(k[i],e[i].Y) < dist(k[i],e[i].X)) e[i] = {e[i].Y,e[i].X};
    int y = (1 << (cnt+1));
    rep(i,1,cnt+2) cost[0][i] = 0;
    ll ans = inf;
    rep(i,1,y){
        rep(j,0,cnt+1){
            if (i&(1 << j)){
                bool f = 1;
                for (int x : in[j+1]) if (!(i&(1 << (x-1)))) f = 0;
                if (!f) break;
                int x = (i - (1 << j));
                if (!x){
                    cost[i][j+1] = dist(s,k[j+1])+dist(k[j+1],e[j+1].X);
                    continue;
                }
                rep(z,0,cnt+1){
                    if (x&(1 << z)){
                        cost[i][j+1] = min(cost[i][j+1],cost[x][z+1]+dist(e[z+1].X,k[j+1])+dist(k[j+1],e[j+1].X));
                    }
                }
            }
        }
        ans = min(ans,cost[i][cnt+1]);
    }
    cout << ans;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 455108 KB Output is correct
2 Correct 210 ms 455096 KB Output is correct
3 Correct 580 ms 489660 KB Output is correct
4 Correct 603 ms 490452 KB Output is correct
5 Correct 579 ms 490380 KB Output is correct
6 Correct 583 ms 489328 KB Output is correct
7 Correct 653 ms 492460 KB Output is correct
8 Correct 606 ms 492604 KB Output is correct
9 Correct 593 ms 492516 KB Output is correct
10 Correct 598 ms 491924 KB Output is correct
11 Correct 624 ms 492420 KB Output is correct
12 Correct 571 ms 489812 KB Output is correct
13 Correct 593 ms 491416 KB Output is correct
14 Correct 614 ms 490064 KB Output is correct
15 Correct 572 ms 482372 KB Output is correct
16 Correct 644 ms 495296 KB Output is correct
17 Correct 593 ms 493272 KB Output is correct
18 Correct 591 ms 494532 KB Output is correct
19 Correct 572 ms 497604 KB Output is correct
20 Correct 585 ms 496068 KB Output is correct
21 Correct 580 ms 497092 KB Output is correct
22 Correct 202 ms 455260 KB Output is correct
23 Correct 208 ms 455184 KB Output is correct
24 Correct 207 ms 455276 KB Output is correct
25 Correct 206 ms 455168 KB Output is correct
26 Correct 210 ms 455260 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 455296 KB Output is correct
2 Correct 209 ms 455152 KB Output is correct
3 Runtime error 632 ms 918904 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 455108 KB Output is correct
2 Correct 210 ms 455096 KB Output is correct
3 Correct 580 ms 489660 KB Output is correct
4 Correct 603 ms 490452 KB Output is correct
5 Correct 579 ms 490380 KB Output is correct
6 Correct 583 ms 489328 KB Output is correct
7 Correct 653 ms 492460 KB Output is correct
8 Correct 606 ms 492604 KB Output is correct
9 Correct 593 ms 492516 KB Output is correct
10 Correct 598 ms 491924 KB Output is correct
11 Correct 624 ms 492420 KB Output is correct
12 Correct 571 ms 489812 KB Output is correct
13 Correct 593 ms 491416 KB Output is correct
14 Correct 614 ms 490064 KB Output is correct
15 Correct 572 ms 482372 KB Output is correct
16 Correct 644 ms 495296 KB Output is correct
17 Correct 593 ms 493272 KB Output is correct
18 Correct 591 ms 494532 KB Output is correct
19 Correct 572 ms 497604 KB Output is correct
20 Correct 585 ms 496068 KB Output is correct
21 Correct 580 ms 497092 KB Output is correct
22 Correct 202 ms 455260 KB Output is correct
23 Correct 208 ms 455184 KB Output is correct
24 Correct 207 ms 455276 KB Output is correct
25 Correct 206 ms 455168 KB Output is correct
26 Correct 210 ms 455260 KB Output is correct
27 Correct 203 ms 455296 KB Output is correct
28 Correct 209 ms 455152 KB Output is correct
29 Runtime error 632 ms 918904 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -