Submission #504019

#	Time	Username	Problem	Language	Result	Execution time	Memory
504019		Victor	Valley (BOI19_valley)	C++17	100 / 100	509 ms	42200 KiB

valley

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const ll INF = 1e17;

struct Node {
    int lo, hi;
    ll madd = 0, val;
    Node *l, *r;

    Node(int L, int R) : lo(L), hi(R) {
        val = INF;
        if (hi - lo != 1) {
            int mid = (lo + hi) / 2;
            l = new Node(lo, mid);
            r = new Node(mid, hi);
        }
    }

    ll query(int L, int R) {
        // cout<<"L = "<<L<<" R = "<<R<<" lo = "<<lo<<" hi = "<<hi<<" val = "<<val<<endl;
        if (hi <= L || R <= lo) return INF;
        if (L <= lo && hi <= R) return val;

        push();
        return min(l->query(L, R), r->query(L, R));
    }

    void add(int L, int R, ll x) {
        if (hi <= L || R <= lo) return;
        if (L <= lo && hi <= R) {
            madd += x;
            val += x;

        } else {
            push();
            l->add(L, R, x);
            r->add(L, R, x);
            val = min(l->val, r->val);
        }
    }

    void push() {
        if (madd) {
            if (hi - lo != 1) {
                l->add(lo, hi, madd);
                r->add(lo, hi, madd);
            }
            madd = 0;
        }
    }
};

int n, s, q, e, euler_pos[100001], depth[100001], sub_size[100001], queries_sub[100001], cnt = 0, order[100001];
ll dist[100001];
vpll graph[100001];
vector<iii> edges;
vii queries[100001];
vi shop;
string ans[100001];
Node *segtree;

void prep(int u, int p, int cur_depth, ll cur_dist) {
    order[cnt] = u;
    euler_pos[u] = cnt++;

    sub_size[u] = 1;
    dist[u] = cur_dist;
    depth[u] = cur_depth;
    
    //cout<<"u = "<<u+1<<" dist = "<<dist[u]<<endl;

    trav(edge, graph[u]) {
        int v, w;
        tie(v, w) = edge;
        if (v != p) {
            prep(v, u, cur_depth + 1, cur_dist + w);
            sub_size[u] += sub_size[v];
            queries_sub[u] += queries_sub[v];
        }
    }
}

void solve(int u, int p) {
    trav(query, queries[u]) {
        int edge, indx;
        tie(edge, indx) = query;

        int a, b, w;
        w = edges[edge].first;
        tie(a, b) = edges[edge].second;
        if (depth[a] > depth[b]) swap(a, b);

        bool work = 1;
        if ((euler_pos[b] <= euler_pos[u] && euler_pos[u] < euler_pos[b] + sub_size[b]) ^ (euler_pos[b] <= euler_pos[e] && euler_pos[e] < euler_pos[b] + sub_size[b])) work = 0;

        if (work)
            ans[indx] = "escaped";
        else {
            ll min_dist;
            if (euler_pos[b] <= euler_pos[u] && euler_pos[u] < euler_pos[b] + sub_size[b]) {
                min_dist = segtree->query(euler_pos[b], euler_pos[b] + sub_size[b]);

            } else {
                min_dist = min(segtree->query(0, euler_pos[b]), segtree->query(euler_pos[b] + sub_size[b], n));
                //rep(i, 0, n) cout << "u = " << i + 1 << " dist = " << segtree->query(euler_pos[i], euler_pos[i] + 1) << endl;
            }
            ans[indx] = to_string(min_dist);
            if (min_dist > 1e15) ans[indx] = "oo";
        }
    }

    trav(edge, graph[u]) {
        int v, w;
        tie(v, w) = edge;
        if (v != p && queries_sub[v]) {
            segtree->add(0, euler_pos[v], w);
            segtree->add(euler_pos[v], euler_pos[v] + sub_size[v], -w);
            segtree->add(euler_pos[v] + sub_size[v], n, w);
            solve(v, u);
            segtree->add(0, euler_pos[v], -w);
            segtree->add(euler_pos[v], euler_pos[v] + sub_size[v], w);
            segtree->add(euler_pos[v] + sub_size[v], n, -w);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    memset(queries_sub, 0, sizeof(queries_sub));
    cin >> n >> s >> q >> e;
    e--;
    segtree = new Node(0, n);

    rep(i, 0, n - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.pb({w, {--u, --v}});
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }

    rep(i, 0, s) {
        int u;
        cin >> u;
        shop.pb(u - 1);
    }

    rep(i, 0, q) {
        int edge, u;
        cin >> edge >> u;
        queries[--u].emplace_back(edge - 1, i);
        ++queries_sub[u];
    }

    prep(0, 0, 0, 0);
    trav(u, shop) segtree->add(euler_pos[u], euler_pos[u]+1, dist[u] - INF);
    
    //rep(i, 0, n) cout << "u = " << i + 1 << " dist = " << segtree->query(euler_pos[i], euler_pos[i] + 1) << endl;
    //cout << endl;
    solve(0, 0);
    rep(i, 0, q) cout << ans[i] << endl;
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void solve(int, int)':
valley.cpp:116:19: warning: variable 'w' set but not used [-Wunused-but-set-variable]
  116 |         int a, b, w;
      |                   ^

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