Submission #603693

#	Time	Username	Problem	Language	Result	Execution time	Memory
603693		LunaMeme	Valley (BOI19_valley)	C++14	23 / 100	357 ms	17236 KiB

valley

#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 = 1e5 + 5;
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(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";
    }
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41