//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimization("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 2e5 + 10, MOD = 1e9 + 7;
const ll INF = 1e18;
struct edge{
int u , w , id;
};
struct hoom{
int u , v , w ;
};
int n , s , q , e , dis[maxn] , t , st[maxn] , fn[maxn];
vector<edge> adj[maxn];
vector<hoom> ed;
vector<int> shop;
bool mark[maxn];
void Dfs(int v , int par){
st[v] = ++t;
for(auto u : adj[v]){
if(u.u != par) Dfs(u.u , v);
}
fn[v] = t;
}
void Sub3(int kh , int ja){
int u = ed[kh].u , v = ed[kh].v , w = ed[kh].w;
if(st[v] < st[u]) swap(u , v);
int f1 = (st[e] >= st[v] and fn[e] <= fn[v] ? 1 : 0);
int f2 = (st[ja] >= st[v] and fn[ja] <= fn[v] ? 1 : 0);
if(f1 == f2) cout << "escaped\n";
else cout << 0 << '\n';
}
void Bfs(int kharab){
queue<int> qu;
fill(dis , dis+maxn , INF);
memset(mark , false , sizeof mark);
for(int u : shop) qu.push(u) , dis[u] = 0 , mark[u] = true;
while(!qu.empty()){
int v = qu.front();
qu.pop();
for(auto u : adj[v]){
if(u.id == kharab or mark[u.u]) continue;
mark[u.u] = true , dis[u.u] = dis[v] + u.w , qu.push(u.u);
}
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin >> n >> s >> q >> e;
ed.pb({0,0,0});
for(int i = 1 ; i < n ; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].pb({v, w, i});
adj[v].pb({u, w, i});
ed.pb({u , v, w});
}
for(int i = 1 ; i <= s ; i++){
int x;
cin >> x;
shop.pb(x);
}
Dfs(1 , 0);
while(q--){
int kharab , ja;
cin >> kharab >> ja;
if(s == n) {
Sub3(kharab , ja);
continue;
}
Bfs(kharab);
int u = ed[kharab].u , v = ed[kharab].v , w = ed[kharab].w;
if(st[v] < st[u]) swap(u , v);
int f1 = (st[e] >= st[v] and fn[e] <= fn[v] ? 1 : 0);
int f2 = (st[ja] >= st[v] and fn[ja] <= fn[v] ? 1 : 0);
if(f1 == f2) cout << "escaped\n";
else {
if(dis[ja] == INF) cout << "oo\n";
else cout << dis[ja] << '\n';
}
}
}
Compilation message
misspelling.cpp: In function 'void Sub3(long long int, long long int)':
misspelling.cpp:40:39: warning: unused variable 'w' [-Wunused-variable]
40 | int u = ed[kh].u , v = ed[kh].v , w = ed[kh].w;
| ^
misspelling.cpp: In function 'int32_t main()':
misspelling.cpp:89:51: warning: unused variable 'w' [-Wunused-variable]
89 | int u = ed[kharab].u , v = ed[kharab].v , w = ed[kharab].w;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
16728 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
16728 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
16476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
16728 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
16728 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
