이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e5+777;
const int MOD = 1e9+7;
const bool I = 1;
int n, s, q, e;
bool mag[N];
bitset<N> used;
int x[N], y[N], w[N];
struct D{
int v, w, id;
};
vector<D> g[N];
bool dfs(int v, int &pp, int p = 1){
// cerr << "v: " << v << '\n';
if(v == e){
return true;
}
used[v] = true;
bool res = false;
for(auto to : g[v]){
if(!used[to.v] && to.id != pp){
res |= dfs(to.v, pp, v);
}
}
return res;
}
int Find(int v, int pp){
int res = 1e9;
vector<int> d(n+1, 1e9);
set<pair<int,int>> st = {{d[v]=0,v}};
while(!st.empty()){
v = st.begin() -> S;
st.erase(st.begin());
if(mag[v]){
res = min(res, d[v]);
}
for(auto to : g[v]){
if(d[to.v] > d[v] + to.w && to.id != pp){
st.erase({d[to.v], to.v});
d[to.v] = d[v] + to.w;
st.insert({d[to.v], to.v});
}
}
}
return res;
}
int main(){NFS;
cin >> n >> s >> q >> e;
for(int i = 1; i < n; ++i){
cin >> x[i] >> y[i] >> w[i];
g[x[i]].pb({y[i], w[i], i});
g[y[i]].pb({x[i], w[i], i});
}
for(int i = 1; i <= s; ++i){
int xx; cin >> xx;
mag[xx] = true;
}
for(int i = 1; i <= q; ++i){
int pp, h;
cin >> pp >> h;
used.reset();
// int cur = dfs(h, pp);
// cerr << "dfs("<<h<<','<<"pp"<<"): " << cur << '\n';
// exit(false);
if(dfs(h, pp)){
cout << "escape\n";
}else{
int cur = Find(h, pp);
if(cur == 1e9) cout << "oo\n";
else cout << cur << '\n';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |