Submission #924718

#	Time	Username	Problem	Language	Result	Execution time	Memory
924718		Karoot	Valley (BOI19_valley)	C++17	100 / 100	322 ms	80192 KiB

valley

    #include <iostream>
    #include <cmath>
    #include <unordered_map>
    #include <map>
    #include <set>
    #include <queue>
    #include <vector>
    #include <string>
    #include <iomanip>
    #include <algorithm>
     
    #define all(x)  (x).begin(), (x).end()
    #define rall(x)  (x).rbegin(), (x).rend()
     
    using namespace std;
     
    typedef long long ll;
     
    ll linf = 1e15+1;
     
    inline void scoobydoobydoo(){
        ios::sync_with_stdio(false);
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
    }
     
    const int MAXN = 1e5+1;
    vector<pair<ll, ll>> adj[MAXN];
    ll parent[MAXN], parentW[MAXN];
    vector<ll> children[MAXN];
    ll depth[MAXN], subSz[MAXN];
    pair<ll, ll> eulerTour[MAXN];
    ll eulerCounter = 0;
    ll closestStore[MAXN];
    bool isStore[MAXN];
     
    ll rootTree(ll node, ll pare, ll w, ll vikt){
        depth[node] = w;
        eulerTour[node].first = eulerCounter++;
        parent[node] = pare;
        parentW[node] = vikt;
        subSz[node] = 1;
     
        ll mini = 1e18;
     
        for (auto p : adj[node]){
            if (p.first == pare)continue;
            subSz[node] += rootTree(p.first, node, w+1, p.second);
            mini = min(mini, closestStore[p.first]+p.second);
            children[node].push_back(p.first);
        }
     
        closestStore[node] = (isStore[node] ? 0 : mini);
     
        eulerTour[node].second = eulerCounter++;
        return subSz[node];
    }
     
    struct Node {
        ll lc, rc;
        ll leftOf, rightOf;
        ll mini, sum;
        Node(){
            lc = -1;
            rc = -1;
            mini = 10000000;
            sum = 0;
            leftOf = -1;
            rightOf = -1;
        }
    };
     
    struct Chain {
        ll tN;
        ll lN;
        ll root;
    };
     
    Node ST[8*MAXN];
    ll counter = 0;
    ll chainC = 0;
    ll nodeToChain[MAXN];
    Chain chains[MAXN];
    ll vals[MAXN];
    ll pW[MAXN];
     
    bool comp(const ll& i1, const ll& i2){
        return subSz[i1] < subSz[i2];
    }
     
    void heavydfs(ll node){
        nodeToChain[node] = chainC;
        sort(rall(children[node]), comp);
        if (children[node].empty()){
            chains[chainC].lN = node;
            return;
        }
        heavydfs(children[node][0]);
     
        for (ll i = 1; i < children[node].size(); i++){
            chainC++;
            chains[chainC].tN = children[node][i];
            heavydfs(children[node][i]);
        }
        return;
    }
     
     
    void buildTree(ll l, ll r, ll node){
        ST[node].leftOf = l;
        ST[node].rightOf = r;
        if (l == r){
            ST[node].mini = vals[l];
            ST[node].sum = pW[l];
            return;
        }
        ll mid = (l+r)>>1;
        ST[node].lc = counter++;
        buildTree(l, mid, ST[node].lc);
        ST[node].rc = counter++;
        buildTree(mid+1, r, ST[node].rc);
        ST[node].mini = min(ST[ST[node].lc].mini+ST[ST[node].rc].sum, ST[ST[node].rc].mini);
        ST[node].sum = ST[ST[node].lc].sum+ST[ST[node].rc].sum;
        return;
    }
     
    void buildSegments(){
        for (ll i = 0; i <= chainC; i++){
            ll howMany = depth[chains[i].lN]-depth[chains[i].tN];
            ll current = chains[i].lN;
            for (ll j = howMany; j >= 0; j--){
                vals[j] = closestStore[current];
                pW[j] = parentW[current];
                current = parent[current];
            }
     
            chains[i].root = counter++;
            buildTree(0, howMany, chains[i].root);
        }
    }
     
    vector<Node> findMother(ll l, ll r, ll node){
        if (l == ST[node].leftOf && r == ST[node].rightOf){
            return {ST[node]};
        }
        ll a = ST[node].lc, b = ST[node].rc;
        if (ST[a].rightOf >= r)return findMother(l, r, a);
        if (ST[b].leftOf <= l)return findMother(l, r, b);
        vector<Node> ret = findMother(l, ST[a].rightOf, a);
        vector<Node> r1 = findMother(ST[b].leftOf, r, b);
        for (Node N : r1)ret.push_back(N);
        return ret;
    }
     
    //summa, mini
    pair<ll, ll> query(ll starting, ll ending, ll chainID, ll startSu){
        ll topp = chains[chainID].tN;
        ll l = depth[ending]-depth[topp];
        ll r = depth[starting]-depth[topp];

        //cout << chainID << "; " << l << " . " << r << endl;
     
        //cout << l << "_" << r << "_" << starting << "_" << ending << "_" << chainID << "_" << startSu << endl;
     
        vector<Node> motherNodes = findMother(l, r, chains[chainID].root);
     
        reverse(all(motherNodes));

        ll su = startSu;
        ll mini = 1e18;
     
        for (Node N : motherNodes){
            mini = min(mini, N.mini+su);
            su += N.sum;
        }
     
        return make_pair(su, mini);
    }
     
    ll indexToNode[MAXN];
     
    int main(){
        scoobydoobydoo();
        //freopen("valley.in", "r", stdin);
        //freopen("valley.ans", "w", stdout);
        ll n, s, q, e; cin >> n >> s >> q >> e;
        vector<vector<ll> > edges;
        for (ll i = 0; i < n-1; i++){
            ll a, b, w; cin >> a >> b >> w;
            a--; b--;
            adj[a].push_back({b, w});
            adj[b].push_back({a, w});
            edges.push_back({a, b, w});
        }
        e--;
     
        for (ll i = 0; i < s; i++){
            ll a; cin >> a;
            a--;
            isStore[a] = true;
        }
     
        rootTree(e, e, 0, 0);
        //cout << "here" << endl;
     
        ll il = 0;
        for (auto v : edges){
            ll a = v[0];
            ll b = v[1];
            if (depth[a] < depth[b]) indexToNode[il] = b;
            else indexToNode[il] = a;
            
            il++;
        }
     
        vector<ll> ans;
     
        /*cout << "closestStore: " << endl;
        for (int i = 0; i < n; i++){
            cout << i << ": " << closestStore[i] << endl;
        }*/
     
        chains[0].tN = e;
     
        heavydfs(e);
     
        buildSegments();
     
        /*cout << "CHAINS:" << endl;
        for (int i = 0; i <= chainC; i++){
            Chain C = chains[i];
            cout << C.lN << " " << C.tN << " " << C.root << endl;
        }*/ 
     
        while (q--){
            ll I, R; cin >> I >> R;
            I--; R--;
            I = indexToNode[I];
            //cout << I << "; " << R << endl;
            if (eulerTour[I].first > eulerTour[R].first || eulerTour[I].second < eulerTour[R].second){
                ans.push_back(-2);
                continue;
            }
            if (closestStore[I] > 1e17){
                ans.push_back(-1);
                continue;
            }
     
            ll sum = 0;
            ll best = 1e18;
            
            ll current = nodeToChain[R];
     
            ll node = R;
     
     
            while (current != nodeToChain[I]){
                pair<ll, ll> p = query(node, chains[current].tN, current, sum);
                
                sum = p.first;
                //if (chains[current].tN != chains[current].lN)sum += parentW[chains[current].tN];
                //sum += parentW[chains[current].tN];
                best = min(best, p.second);
                node = parent[chains[current].tN];
                
                //cout << p.first << " + " << p.second << endl;

                current = nodeToChain[node];
            }
     
            pair<ll, ll> p = query(node, I, current, sum);
            //cout << p.first << " + " << p.second << endl;
            best = min(best, p.second);
            ans.push_back(best);
        }
     
     
        for (ll x : ans){
            if (x == -1)cout << "oo" << endl;
            else if (x == -2)cout << "escaped" << endl;
            else cout << x << endl;
        }
     
     
     
     
        return 0;
    }

Compilation message (stderr)

valley.cpp: In function 'void heavydfs(ll)':
valley.cpp:100:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (ll i = 1; i < children[node].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~

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