oj.uz

Submission #603693

# Submission time Handle Problem Language Result Execution time Memory
603693 2022-07-24T09:49:07 Z LunaMeme Valley (BOI19_valley) C++14
23 / 100
 357 ms 17236 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 14680 KB Output is correct
2 Correct 338 ms 14320 KB Output is correct
3 Correct 354 ms 14204 KB Output is correct
4 Correct 315 ms 15680 KB Output is correct
5 Correct 313 ms 15768 KB Output is correct
6 Correct 357 ms 17236 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -