oj.uz

Submission #470216

# Submission time Handle Problem Language Result Execution time Memory
470216 2021-09-03T09:32:19 Z radal LOSTIKS (INOI20_lostiks) C++14
0 / 100
 435 ms 93124 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];
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;
    queue<int> q;
    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;
    }
    rep(i,1,cnt+1){
        if (!din[i]){
            q.push(i);
        }
    }
    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);
        }
    }
    int v = s,p = 0;
    ll ans = 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++;
    }
    cout << ans;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 54336 KB Output is correct
2 Correct 31 ms 54300 KB Output is correct
3 Correct 384 ms 88716 KB Output is correct
4 Correct 435 ms 89532 KB Output is correct
5 Correct 404 ms 89536 KB Output is correct
6 Correct 383 ms 88348 KB Output is correct
7 Correct 422 ms 92844 KB Output is correct
8 Correct 409 ms 93008 KB Output is correct
9 Correct 408 ms 93124 KB Output is correct
10 Correct 413 ms 92200 KB Output is correct
11 Correct 415 ms 92740 KB Output is correct
12 Correct 411 ms 90320 KB Output is correct
13 Incorrect 427 ms 91972 KB Output isn't correct
14 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 31 ms 54340 KB Output is correct
3 Incorrect 31 ms 54344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 54336 KB Output is correct
2 Correct 31 ms 54300 KB Output is correct
3 Correct 384 ms 88716 KB Output is correct
4 Correct 435 ms 89532 KB Output is correct
5 Correct 404 ms 89536 KB Output is correct
6 Correct 383 ms 88348 KB Output is correct
7 Correct 422 ms 92844 KB Output is correct
8 Correct 409 ms 93008 KB Output is correct
9 Correct 408 ms 93124 KB Output is correct
10 Correct 413 ms 92200 KB Output is correct
11 Correct 415 ms 92740 KB Output is correct
12 Correct 411 ms 90320 KB Output is correct
13 Incorrect 427 ms 91972 KB Output isn't correct
14 Halted 0 ms 0 KB -