oj.uz

Submission #470226

# Submission time Handle Problem Language Result Execution time Memory
470226 2021-09-03T09:51:24 Z radal LOSTIKS (INOI20_lostiks) C++14
0 / 100
 476 ms 96704 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({min(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({min(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 31 ms 54340 KB Output is correct
2 Correct 31 ms 54348 KB Output is correct
3 Correct 400 ms 88840 KB Output is correct
4 Correct 415 ms 89608 KB Output is correct
5 Correct 440 ms 89660 KB Output is correct
6 Correct 432 ms 88324 KB Output is correct
7 Correct 462 ms 91656 KB Output is correct
8 Correct 476 ms 91716 KB Output is correct
9 Correct 427 ms 91608 KB Output is correct
10 Correct 401 ms 90976 KB Output is correct
11 Correct 463 ms 91716 KB Output is correct
12 Correct 475 ms 89028 KB Output is correct
13 Correct 397 ms 90564 KB Output is correct
14 Correct 417 ms 89188 KB Output is correct
15 Correct 439 ms 81604 KB Output is correct
16 Correct 423 ms 94444 KB Output is correct
17 Correct 409 ms 92480 KB Output is correct
18 Correct 425 ms 93568 KB Output is correct
19 Correct 407 ms 96704 KB Output is correct
20 Correct 456 ms 95148 KB Output is correct
21 Correct 408 ms 96256 KB Output is correct
22 Correct 32 ms 54348 KB Output is correct
23 Correct 31 ms 54328 KB Output is correct
24 Incorrect 30 ms 54348 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

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

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 54340 KB Output is correct
2 Correct 31 ms 54348 KB Output is correct
3 Correct 400 ms 88840 KB Output is correct
4 Correct 415 ms 89608 KB Output is correct
5 Correct 440 ms 89660 KB Output is correct
6 Correct 432 ms 88324 KB Output is correct
7 Correct 462 ms 91656 KB Output is correct
8 Correct 476 ms 91716 KB Output is correct
9 Correct 427 ms 91608 KB Output is correct
10 Correct 401 ms 90976 KB Output is correct
11 Correct 463 ms 91716 KB Output is correct
12 Correct 475 ms 89028 KB Output is correct
13 Correct 397 ms 90564 KB Output is correct
14 Correct 417 ms 89188 KB Output is correct
15 Correct 439 ms 81604 KB Output is correct
16 Correct 423 ms 94444 KB Output is correct
17 Correct 409 ms 92480 KB Output is correct
18 Correct 425 ms 93568 KB Output is correct
19 Correct 407 ms 96704 KB Output is correct
20 Correct 456 ms 95148 KB Output is correct
21 Correct 408 ms 96256 KB Output is correct
22 Correct 32 ms 54348 KB Output is correct
23 Correct 31 ms 54328 KB Output is correct
24 Incorrect 30 ms 54348 KB Output isn't correct
25 Halted 0 ms 0 KB -