| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 624112 | Arinoor | LOSTIKS (INOI20_lostiks) | C++17 | 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>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define bug(x) cout << #x << " : " << x << '\n'
#define ios ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 10;
const int maxm = 30;
const int maxlg = 20;
const int mod = 1e9 + 7;
const ll inf = 1e17 + 10;
int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
int dt[maxm], dl[maxm];
int d[maxm][maxm], l[maxm][maxm];
ll dp[1 << maxlg][maxm];
vector<pii> E;
vector<pii> edge;
vector<int> G[maxn], S;
void dfs(int v, int p = 0, int pe = -1){
par[v][0] = p;
if(~pe)
lck[v][0] = 1 << pe;
for(int i = 1; i < maxlg and par[v][i - 1]; i ++){
par[v][i] = par[par[v][i - 1]][i - 1];
lck[v][i] = lck[v][i - 1] | lck[par[v][i - 1]][i - 1];
}
for(int eg : G[v]){
int u = edge[eg].fi + edge[eg].se - v;
if(u != p){
h[u] = h[v] + 1;
dfs(u, v, e[eg]);
}
}
}
int get_par(int v, int h){
for(int i = 0; i < maxlg; i ++)
if(h >> i & 1)
v = par[v][i];
return v;
}
int get_lock(int v, int h){
int res = 0;
for(int i = 0; i < maxlg; i ++){
if(h >> i & 1){
res |= lck[v][i];
v = par[v][i];
}
}
return res;
}
int lca(int v, int u){
if(h[v] < h[u])
swap(u, v);
v = get_par(v, h[v] - h[u]);
if(v == u)
return v;
for(int i = maxlg - 1; ~i; i --){
if(par[v][i] ^ par[u][i]){
v = par[v][i];
u = par[u][i];
}
}
return par[v][0];
}
int dist(int u, int v){
int w = lca(u, v);
return h[v] + h[u] - 2 * h[w];
}
int lock_path(int u, int v){
int w = lca(u, v);
return get_lock(u, h[u] - h[w]) | get_lock(v, h[v] - h[w]);
}
int main(){
ios;
int n, s, t;
cin >> n >> s >> t;
for(int i = 0; i < n - 1; i ++){
int u, v, w;
cin >> u >> v >> w;
edge.pb(mp(u, v));
G[u].pb(i);
G[v].pb(i);
if(w){
e[i] = E.size();
E.pb(mp(i, w));
}
else{
e[i] = -1;
}
}
dfs(1);
int m = E.size();
for(int i = 0; i < m; i ++){
int u = edge[E[i].fi].fi;
int v = edge[E[i].fi].se;
if(dist(E[i].se, u) < dist(E[i].se, v))
V[i] = u;
else
V[i] = v;
S.pb(V[i]);
}
S.pb(s);
sort(all(S));
S.resize(unique(all(S)) - S.begin());
for(int v : S)
ind[v] = lower_bound(all(S), v) - S.begin();
n = S.size();
for(int i = 0; i < n; i ++){
int v = S[i];
dt[i] = dist(v, t);
dl[i] = lock_path(v, t);
for(int j = 0; j < m; j ++){
int u = V[j];
int w = E[j].se;
d[i][j] = dist(v, w) + dist(w, u);
l[i][j] = lock_path(v, w) | lock_path(w, u);
}
}
for(int msk = 0; msk < 1 << m; msk ++){
for(int i = 0; i < n; i ++){
if(!(dl[i] & msk)){
dp[msk][i] = dt[i];
continue;
}
dp[msk][i] = inf;
for(int msk2 = msk; ; msk2 -= msk2 & -msk2){
if(!msk2) break;
int bit = __builtin_ctz(msk2);
if(!(l[i][bit] & msk)){
dp[msk][i] = min(dp[msk][i], d[i][bit] + dp[msk ^ (1 << bit)][ind[V[bit]]]);
}
}
}
}
if(dp[(1 << m) - 1][ind[s]] >= inf)
cout << "-1\n";
else
cout << dp[(1 << m) - 1][ind[s]] << '\n';
}#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define bug(x) cout << #x << " : " << x << '\n'
#define ios ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 10;
const int maxm = 30;
const int maxlg = 20;
const int mod = 1e9 + 7;
const ll inf = 1e17 + 10;
int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
int dt[maxm], dl[maxm];
int d[maxm][maxm], l[maxm][maxm];
ll dp[1 << maxlg][maxm];
vector<pii> E;
vector<pii> edge;
vector<int> G[maxn], S;
void dfs(int v, int p = 0, int pe = -1){
par[v][0] = p;
if(~pe)
lck[v][0] = 1 << pe;
for(int i = 1; i < maxlg and par[v][i - 1]; i ++){
par[v][i] = par[par[v][i - 1]][i - 1];
lck[v][i] = lck[v][i - 1] | lck[par[v][i - 1]][i - 1];
}
for(int eg : G[v]){
int u = edge[eg].fi + edge[eg].se - v;
if(u != p){
h[u] = h[v] + 1;
dfs(u, v, e[eg]);
}
}
}
int get_par(int v, int h){
for(int i = 0; i < maxlg; i ++)
if(h >> i & 1)
v = par[v][i];
return v;
}
int get_lock(int v, int h){
int res = 0;
for(int i = 0; i < maxlg; i ++){
if(h >> i & 1){
res |= lck[v][i];
v = par[v][i];
}
}
return res;
}
int lca(int v, int u){
if(h[v] < h[u])
swap(u, v);
v = get_par(v, h[v] - h[u]);
if(v == u)
return v;
for(int i = maxlg - 1; ~i; i --){
if(par[v][i] ^ par[u][i]){
v = par[v][i];
u = par[u][i];
}
}
return par[v][0];
}
int dist(int u, int v){
int w = lca(u, v);
return h[v] + h[u] - 2 * h[w];
}
int lock_path(int u, int v){
int w = lca(u, v);
return get_lock(u, h[u] - h[w]) | get_lock(v, h[v] - h[w]);
}
int main(){
ios;
int n, s, t;
cin >> n >> s >> t;
for(int i = 0; i < n - 1; i ++){
int u, v, w;
cin >> u >> v >> w;
edge.pb(mp(u, v));
G[u].pb(i);
G[v].pb(i);
if(w){
e[i] = E.size();
E.pb(mp(i, w));
}
else{
e[i] = -1;
}
}
dfs(1);
int m = E.size();
for(int i = 0; i < m; i ++){
int u = edge[E[i].fi].fi;
int v = edge[E[i].fi].se;
if(dist(E[i].se, u) < dist(E[i].se, v))
V[i] = u;
else
V[i] = v;
S.pb(V[i]);
}
S.pb(s);
sort(all(S));
S.resize(unique(all(S)) - S.begin());
for(int v : S)
ind[v] = lower_bound(all(S), v) - S.begin();
n = S.size();
for(int i = 0; i < n; i ++){
int v = S[i];
dt[i] = dist(v, t);
dl[i] = lock_path(v, t);
for(int j = 0; j < m; j ++){
int u = V[j];
int w = E[j].se;
d[i][j] = dist(v, w) + dist(w, u);
l[i][j] = lock_path(v, w) | lock_path(w, u);
}
}
for(int msk = 0; msk < 1 << m; msk ++){
for(int i = 0; i < n; i ++){
if(!(dl[i] & msk)){
dp[msk][i] = dt[i];
continue;
}
dp[msk][i] = inf;
for(int msk2 = msk; ; msk2 -= msk2 & -msk2){
if(!msk2) break;
int bit = __builtin_ctz(msk2);
if(!(l[i][bit] & msk)){
dp[msk][i] = min(dp[msk][i], d[i][bit] + dp[msk ^ (1 << bit)][ind[V[bit]]]);
}
}
}
}
if(dp[(1 << m) - 1][ind[s]] >= inf)
cout << "-1\n";
else
cout << dp[(1 << m) - 1][ind[s]] << '\n';
}