제출 #496452

#제출 시각아이디문제언어결과실행 시간메모리
496452IerusValley (BOI19_valley)C++17
0 / 100
159 ms30448 KiB
#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 int long long #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 = LLONG_MAX; vector<int> d(n+1, LLONG_MAX); 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; } const int LG = 19; int up[N][LG+2], tin[N], tout[N], timer; void dfs1(int v, int p = 0) { tin[v] = ++timer; up[v][0] = p; for (int i = 1; i <= LG; ++i) up[v][i] = up[up[v][i-1]][i-1]; for (auto to : g[v]) { if (to.v != p) dfs1(to.v, v); } tout[v] = timer; } bool upper(int a, int b) { return tin[a] <= tin[b] && tout[b] <= tout[a] ; } int lca (int a, int b) { if (upper (a, b)) return a; if (upper (b, a)) return b; for (int i = LG; i>=0; --i) if (!upper(up[a][i], b)) a = up[a][i]; return up[a][0]; } signed 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; } // if(n <= 1000 && q <= 10000){ // for(int i = 1; i <= q; ++i){ // int pp, h; // cin >> pp >> h; // used.reset(); // if(dfs(h, pp)){ // cout << "escaped\n"; // }else{ // int cur = Find(h, pp); // if(cur == LLONG_MAX) cout << "oo\n"; // else cout << cur << '\n'; // } // } // exit(false); // } dfs1(1, 1); for(int i = 1; i <= q; ++i){ int pp, h; cin >> pp >> h; int lc = lca(h, e); if((lca(e, x[pp]) == x[pp] && lca(x[pp], lc) == lc) || (lca(e, y[pp]) == y[pp] && lca(y[pp], lc) == lc)){ cout << "0\n"; continue; } cout << "escaped\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...