Submission #470274

#	Time	Username	Problem	Language	Result	Execution time	Memory
470274		radal	LOSTIKS (INOI20_lostiks)	C++14	23 / 100	653 ms	918904 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,maxm = (1 << 9),inf = 1e18;
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],par[N][20],h[N],mark[N],din2[N],din3[N],din4[N];
vector<int> dp[N][22],out[22],in[22];
ll cost[maxm][N];
pll e[22];
int cnt;
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 != cnt+1) dp[w.X][v].pb(cnt+1);
        }
    }
    vis.reset();
}
bool pre(int v){
    mark[v] = 1;
    for (int u : dp[s][v]){
        out[u].pb(v);
        in[v].pb(u);
        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);
            in[v].pb(u);
            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);
            in[v].pb(u);
            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(cost,63,sizeof cost);
    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[cnt+1] = t;
    rep(i,1,cnt+2) bfs(i);
    e[cnt+1] = {t,t};
    if (!pre(cnt+1)){
        cout << -1;
        return 0;
    }
    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];
        }
    }
    rep(i,1,cnt+1) if(dist(k[i],e[i].Y) < dist(k[i],e[i].X)) e[i] = {e[i].Y,e[i].X};
    int y = (1 << (cnt+1));
    rep(i,1,cnt+2) cost[0][i] = 0;
    ll ans = inf;
    rep(i,1,y){
        rep(j,0,cnt+1){
            if (i&(1 << j)){
                bool f = 1;
                for (int x : in[j+1]) if (!(i&(1 << (x-1)))) f = 0;
                if (!f) break;
                int x = (i - (1 << j));
                if (!x){
                    cost[i][j+1] = dist(s,k[j+1])+dist(k[j+1],e[j+1].X);
                    continue;
                }
                rep(z,0,cnt+1){
                    if (x&(1 << z)){
                        cost[i][j+1] = min(cost[i][j+1],cost[x][z+1]+dist(e[z+1].X,k[j+1])+dist(k[j+1],e[j+1].X));
                    }
                }
            }
        }
        ans = min(ans,cost[i][cnt+1]);
    }
    cout << ans;
}

• Subtask 1: 23 / 23
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41