| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 470277 | radal | LOSTIKS (INOI20_lostiks) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 2e3+20,mod = 1e9+7,maxm = (1 << 22),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;
}