| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 470217 |
2021-09-03T09:36:48 Z |
radal |
LOSTIKS (INOI20_lostiks) |
C++14 |
|
82 ms |
109924 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],din2[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;
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;
rep(i,1,cnt+1){
din2[i] = din[i];
if (!din[i]){
q.push(i);
st.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);
}
}
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);
}
}
int v = s,p = 0;
ll ans = 0,ans2 = 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++;
}
cout << min(ans,ans2);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
82 ms |
109896 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
79 ms |
109924 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
82 ms |
109896 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
