Submission #603808

#	Time	Username	Problem	Language	Result	Execution time	Memory
603808		LunaMeme	Valley (BOI19_valley)	C++14	9 / 100	22 ms	2004 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 = 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
ii level[MAXN];
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;
        ll w = pr.second;
        if (next == par) continue;
        dist[next] = dist[curr] + w;
        level[next] = MP(level[curr].first + 1, next);
        dfs(next, curr);
        indx ++;
        tour.PB(curr);
        subtree[curr].second = indx;
    }
}
int pow_2 = 1;
void update(int i, ii val);
ii query(int l, int r);
int lca(int a , int b);
ll dist_in(int a,int b);
bool can_go(int a, int b, int des);
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;
    level[e] = MP(0, e);
    dfs(e, -1);
    while(pow_2 < (int)tour.size()){
        pow_2 *= 2;
    }
    FOR(i, 0, 4*MAXN) segtree[i] = {1e9, 1e9};
    for(auto i : tour){
        //cout << i << " " << level[i].first << " " << level[i].second << '\n';
        arr.PB(level[i]);
    }
    int j = 0;
    for(auto pr : arr){
        update(j, pr);
        j++;
        //cout << pr.first << ' '<< pr.second << '\n';
    } 
    //FOR(i, 1, 2 * tour.size() + 1) cout << segtree[i].first << ',' << segtree[i].second << "  ";
    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 r 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;
        }
        ll mn_dist = 1e18;
        for(int t = s-1; t >= 0; t --){
            //cout << dist_in(shops[t], r) << '\n';
            if (can_go(r, shops[t], dest)){
                mn_dist = min(mn_dist, dist_in(shops[t], r));
            }
        }
        if (mn_dist == 1e18) cout << "oo\n";
        else cout << mn_dist << '\n';
    }
}
void update(int i, ii val){
    i += pow_2;
    segtree[i] = val;
    //cout << i << "  VALUE : " << val.first << ' ' << val.second << '\n';
    while(i /= 2){
        segtree[i] = min(segtree[2*i], segtree[2*i + 1]);
    }
}
ii query(int l, int r){
    l += pow_2; r += pow_2;
    if (r <l) swap(l ,r);
    ii ans =MP(1e9, 0);
    while(r > l && l >  0){
        //cout << "LEFT : " << l << "  RIGHT : " << r << '\n';
        if (l % 2 == 1){
            //cout << segtree[l].first << ' '<< segtree[l].second << '\n';
            ans = min(ans, segtree[l]);
            l ++;
        }
        if (r % 2 == 0){
            ans = min(ans, segtree[r]);
            r --;
        }
        l/= 2; r /=2;
        //cout <<"ANSWER: " <<  ans.first << ' ' << ans.second << '\n';
    }
    if (l)
        ans = min(ans, segtree[l]);
    return ans;
}
int lca(int a , int b){
    int l = subtree[a].second;
    int r = subtree[b].second;
    int l1 = subtree[a].first;
    int r1 = subtree[b].first;
    //cout << a << ' ' << b << ' ' << l << ' ' << r << '\n';
    //assert(query(l, r).second == query(l1, r1).second);
    return query(l1, r1).second;
}
ll dist_in(int a,int b){
    //cout << a << ' ' << b << ' ' << lca(a, b) << '\n';
    //cout << dist[a] << ' ' << dist[b] << ' ' << dist[lca(a, b)] << '\n';
    return dist[a] + dist[b] - 2*dist[lca(a,b)];
}
bool can_go(int a, int b, int dest){
    return (((subtree[a].first < subtree[dest].first || subtree[a].second > subtree[dest].second) && (subtree[b].first < subtree[dest].first || subtree[b].second > subtree[dest].second)) ||((subtree[a].first >= subtree[dest].first && subtree[a].second <= subtree[dest].second) && subtree[b].first >= subtree[dest].first && subtree[b].second <= subtree[dest].second));
}

Compilation message (stderr)

valley.cpp: In function 'int lca(int, int)':
valley.cpp:130:9: warning: unused variable 'l' [-Wunused-variable]
  130 |     int l = subtree[a].second;
      |         ^
valley.cpp:131:9: warning: unused variable 'r' [-Wunused-variable]
  131 |     int r = subtree[b].second;
      |         ^

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