Submission #470222

#	Time	Username	Problem	Language	Result	Execution time	Memory
470222		radal	LOSTIKS (INOI20_lostiks)	C++14	0 / 100	473 ms	96708 KiB

Main

#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
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41