oj.uz

Submission #470222

# Submission time Handle Problem Language Result Execution time Memory
470222 2021-09-03T09:46:05 Z radal LOSTIKS (INOI20_lostiks) C++14
0 / 100
 473 ms 96708 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];
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;
    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;
    rep(i,1,cnt+1){
        din2[i] = din3[i] = din[i];
        if (!din[i]){
            q.push(i);
            st.push(i);
            pq.push({dist(e[i].X,t),i});
        }
    }
    din2[21] = din3[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});
        }
    }
    int v = s,p = 0;
    ll ans = 0,ans2 = 0,ans3 = 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++;
    }
    cout << min({ans3,ans,ans2});
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 54348 KB Output is correct
2 Correct 30 ms 54244 KB Output is correct
3 Correct 404 ms 88744 KB Output is correct
4 Correct 424 ms 89560 KB Output is correct
5 Correct 392 ms 89556 KB Output is correct
6 Correct 403 ms 88404 KB Output is correct
7 Correct 437 ms 91568 KB Output is correct
8 Correct 414 ms 91716 KB Output is correct
9 Correct 456 ms 91672 KB Output is correct
10 Correct 427 ms 90980 KB Output is correct
11 Correct 426 ms 91504 KB Output is correct
12 Correct 406 ms 89084 KB Output is correct
13 Correct 408 ms 90544 KB Output is correct
14 Correct 421 ms 89268 KB Output is correct
15 Correct 401 ms 81424 KB Output is correct
16 Correct 450 ms 94444 KB Output is correct
17 Correct 473 ms 92536 KB Output is correct
18 Correct 420 ms 93588 KB Output is correct
19 Correct 437 ms 96708 KB Output is correct
20 Correct 434 ms 95352 KB Output is correct
21 Correct 414 ms 96196 KB Output is correct
22 Correct 29 ms 54396 KB Output is correct
23 Correct 30 ms 54348 KB Output is correct
24 Incorrect 32 ms 54392 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 54348 KB Output is correct
2 Correct 32 ms 54308 KB Output is correct
3 Correct 31 ms 54344 KB Output is correct
4 Incorrect 30 ms 54348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 54348 KB Output is correct
2 Correct 30 ms 54244 KB Output is correct
3 Correct 404 ms 88744 KB Output is correct
4 Correct 424 ms 89560 KB Output is correct
5 Correct 392 ms 89556 KB Output is correct
6 Correct 403 ms 88404 KB Output is correct
7 Correct 437 ms 91568 KB Output is correct
8 Correct 414 ms 91716 KB Output is correct
9 Correct 456 ms 91672 KB Output is correct
10 Correct 427 ms 90980 KB Output is correct
11 Correct 426 ms 91504 KB Output is correct
12 Correct 406 ms 89084 KB Output is correct
13 Correct 408 ms 90544 KB Output is correct
14 Correct 421 ms 89268 KB Output is correct
15 Correct 401 ms 81424 KB Output is correct
16 Correct 450 ms 94444 KB Output is correct
17 Correct 473 ms 92536 KB Output is correct
18 Correct 420 ms 93588 KB Output is correct
19 Correct 437 ms 96708 KB Output is correct
20 Correct 434 ms 95352 KB Output is correct
21 Correct 414 ms 96196 KB Output is correct
22 Correct 29 ms 54396 KB Output is correct
23 Correct 30 ms 54348 KB Output is correct
24 Incorrect 32 ms 54392 KB Output isn't correct
25 Halted 0 ms 0 KB -