# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
603689 | LunaMeme | Valley (BOI19_valley) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int , int > ii;
typedef vector<ii> vii;
#define MP make_pair
#define PB push_back
#define FOR(i, x, y) for(int i = x; i < y; i ++)
const int MAXN = 1e3 + 5;
ii segtree[4*MAXN]; //segtree on levels
vi tour;
vii arr;
int n,s , q, e;
vii adj[MAXN];
int indx = -1;
vii subtree(MAXN, {-1, -1});
ll dist[MAXN]; // distance from root
void dfs(int curr, int par){
indx ++;
tour.PB(curr);
if (subtree[curr].first == -1){
subtree[curr].first = indx;
}
subtree[curr].second = indx;
for (auto pr : adj[curr]){
int next = pr.first, w = pr.second;
if (next == par) continue;
dist[next] = dist[curr] + w;
dfs(next, curr);
indx ++;
tour.PB(curr);
subtree[curr].second = indx;
}
}
int shops[MAXN];
int main(){
cin >> n >> s >> q >> e;
vii edges(n - 1);
FOR(i, 0, n- 1){
int a, b, w; cin >>a >> b >> w;
adj[a].PB(MP(b, w));
adj[b].PB(MP(a, w));
edges[i] = MP(a,b);
}
//root at e
dist[e] = 0;
dfs(e, -1);
for(auto i : tour){
//cout << i << " " << level[i].first << " " << level[i].second << '\n';
arr.PB(level[i]);
}
FOR(i, 0, s) cin >> shops[i];
FOR(k, 0, q){
int i , r; cin >> i >> r;
ii pr = edges[i - 1];
int dest;
if (dist[pr.first] < dist[pr.second])
dest = pr.second;
else dest = pr.first;
//check if i in dest subtree or not
if (subtree[r].first < subtree[dest].first || subtree[r].second > subtree[dest].second){
//cout << r << ' ' << dest << '\n';
cout << "escaped\n";
continue;
}
cout << "0\n";
}
}