oj.uz

Submission #470229

# Submission time Handle Problem Language Result Execution time Memory
470229 2021-09-03T09:53:42 Z radal LOSTIKS (INOI20_lostiks) C++14
0 / 100
 517 ms 96724 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;
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],din[22],par[N][20],h[N],mark[N],din2[N],din3[N],din4[N];
vector<int> dp[N][22],out[22];
pll e[22];
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 != 21) dp[w.X][v].pb(21);
        }
    }
    vis.reset();
}
bool pre(int v){
    mark[v] = 1;
    din[v] = 0;
    for (int u : dp[s][v]){
        din[v]++;
        out[u].pb(v);
        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);
            din[v]++;
            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);
            din[v]++;
            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(din,-1,sizeof din);
    int cnt = 0;
    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[21] = t;
    rep(i,1,cnt+1) bfs(i);
    bfs(21);
    e[21] = {t,t};
    if (!pre(21)){
        cout << -1;
        return 0;
    }
    vector<int> ve,ve2,ve3,ve4;
    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];
        }
    }
    if (!din[21]){
        cout << dist(s,t);
        return 0;
    }
    queue<int> q;
    stack<int> st;
    priority_queue<pll> pq,pq2;
    rep(i,1,cnt+1){
        din2[i] = din3[i] = din4[i] = din[i];
        if (!din[i]){
            q.push(i);
            st.push(i);
            pq.push({dist(e[i].X,t),i});
            pq2.push({max(dist(e[i].X,t),dist(e[i].Y,t)),i});
        }
    }
    din2[21] = din3[21] = din4[21] = din[21];
    while (!q.empty()){
        int v = q.front();
        q.pop();
        ve.pb(v);
        for (int u : out[v]){
            din[u]--;
            if (!din[u]) q.push(u);
        }
    }
    while (!st.empty()){
        int v = st.top();
        st.pop();
        ve2.pb(v);
        for (int u : out[v]){
            din2[u]--;
            if (!din2[u]) st.push(u);
        }
    }
    while (!pq.empty()){
        int v = pq.top().Y;
        pq.pop();
        ve3.pb(v);
        for (int u : out[v]){
            din3[u]--;
            if (!din3[u]) pq.push({dist(t,e[u].X),u});
        }
    }
    while (!pq2.empty()){
        int v = pq2.top().Y;
        pq2.pop();
        ve4.pb(v);
        for (int u : out[v]){
            din4[u]--;
            if (!din4[u]) pq2.push({max(dist(t,e[u].Y),dist(t,e[u].X)),u});
        }
    }
    int v = s,p = 0;
    ll ans = 0,ans2 = 0,ans3 = 0,ans4 = 0;
    while (v != t){
        int u = ve[p];
        if (u == 21){
            ans += dist(v,t);
            break;
        }
        ans += dist(v,k[u]);
        int w1 = dist(k[u],e[u].X),w2 = dist(k[u],e[u].Y);
        if (w1 <= w2){
            v = e[u].X;
            ans += w1;
        }
        else{
            v = e[u].Y;
            ans+=w2;
        }
        p++;
    }
    v = s,p = 0;
    while (v != t){
        int u = ve2[p];
        if (u == 21){
            ans2 += dist(v,t);
            break;
        }
        ans2 += dist(v,k[u]);
        int w1 = dist(k[u],e[u].X),w2 = dist(k[u],e[u].Y);
        if (w1 <= w2){
            v = e[u].X;
            ans2 += w1;
        }
        else{
            v = e[u].Y;
            ans2 += w2;
        }
        p++;
    }
    v = s, p = 0;
    while (v != t){
        int u = ve3[p];
        if (u == 21){
            ans3 += dist(v,t);
            break;
        }
        ans3 += dist(v,k[u]);
        int w1 = dist(k[u],e[u].X),w2 = dist(k[u],e[u].Y);
        if (w1 <= w2){
            v = e[u].X;
            ans3 += w1;
        }
        else{
            v = e[u].Y;
            ans3 += w2;
        }
        p++;
    }
    v = s, p =0;
    while (v != t){
        int u = ve4[p];
        if (u == 21){
            ans4 += dist(v,t);
            break;
        }
        ans4 += dist(v,k[u]);
        int w1 = dist(k[u],e[u].X),w2 = dist(k[u],e[u].Y);
        if (w1 <= w2){
            v = e[u].X;
            ans4 += w1;
        }
        else{
            v = e[u].Y;
            ans4 += w2;
        }
        p++;
    }
    cout << min({ans3,ans,ans2,ans4});
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 54348 KB Output is correct
2 Correct 36 ms 54280 KB Output is correct
3 Correct 477 ms 88948 KB Output is correct
4 Correct 435 ms 89652 KB Output is correct
5 Correct 454 ms 89636 KB Output is correct
6 Correct 452 ms 88480 KB Output is correct
7 Correct 502 ms 91668 KB Output is correct
8 Correct 505 ms 91856 KB Output is correct
9 Correct 484 ms 91584 KB Output is correct
10 Correct 467 ms 91056 KB Output is correct
11 Correct 493 ms 91536 KB Output is correct
12 Correct 453 ms 89016 KB Output is correct
13 Correct 490 ms 90672 KB Output is correct
14 Correct 496 ms 89196 KB Output is correct
15 Correct 421 ms 81540 KB Output is correct
16 Correct 517 ms 94444 KB Output is correct
17 Correct 481 ms 92424 KB Output is correct
18 Correct 441 ms 93672 KB Output is correct
19 Correct 481 ms 96724 KB Output is correct
20 Correct 494 ms 95364 KB Output is correct
21 Correct 489 ms 96220 KB Output is correct
22 Correct 35 ms 54348 KB Output is correct
23 Correct 37 ms 54352 KB Output is correct
24 Incorrect 43 ms 54436 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 54264 KB Output is correct
2 Correct 36 ms 54284 KB Output is correct
3 Correct 38 ms 54432 KB Output is correct
4 Incorrect 37 ms 54396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 54348 KB Output is correct
2 Correct 36 ms 54280 KB Output is correct
3 Correct 477 ms 88948 KB Output is correct
4 Correct 435 ms 89652 KB Output is correct
5 Correct 454 ms 89636 KB Output is correct
6 Correct 452 ms 88480 KB Output is correct
7 Correct 502 ms 91668 KB Output is correct
8 Correct 505 ms 91856 KB Output is correct
9 Correct 484 ms 91584 KB Output is correct
10 Correct 467 ms 91056 KB Output is correct
11 Correct 493 ms 91536 KB Output is correct
12 Correct 453 ms 89016 KB Output is correct
13 Correct 490 ms 90672 KB Output is correct
14 Correct 496 ms 89196 KB Output is correct
15 Correct 421 ms 81540 KB Output is correct
16 Correct 517 ms 94444 KB Output is correct
17 Correct 481 ms 92424 KB Output is correct
18 Correct 441 ms 93672 KB Output is correct
19 Correct 481 ms 96724 KB Output is correct
20 Correct 494 ms 95364 KB Output is correct
21 Correct 489 ms 96220 KB Output is correct
22 Correct 35 ms 54348 KB Output is correct
23 Correct 37 ms 54352 KB Output is correct
24 Incorrect 43 ms 54436 KB Output isn't correct
25 Halted 0 ms 0 KB -