Submission #603759

#	Time	Username	Problem	Language	Result	Execution time	Memory
603759		LunaMeme	Valley (BOI19_valley)	C++14	0 / 100	18 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 < 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(t, 0, s){
                //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';
        }
        ans = min(ans, segtree[l]);
        return ans;
    }
    int lca(int a , int b){
        int l = subtree[a].first;
        int r = subtree[b].first;
        //cout << a << ' ' << b << ' ' << l << ' ' << r << '\n';
        return query(l, r).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 main()':
valley.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         while(pow_2 < tour.size()){
      |               ~~~~~~^~~~~~~~~~~~~

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