oj.uz

Submission #504019

# Submission time Handle Problem Language Result Execution time Memory
504019 2022-01-09T14:03:23 Z Victor Valley (BOI19_valley) C++17
100 / 100
 509 ms 42200 KB 
// #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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8744 KB Output is correct
2 Correct 18 ms 8752 KB Output is correct
3 Correct 18 ms 8792 KB Output is correct
4 Correct 21 ms 8680 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8744 KB Output is correct
2 Correct 18 ms 8752 KB Output is correct
3 Correct 18 ms 8792 KB Output is correct
4 Correct 21 ms 8680 KB Output is correct
5 Correct 7 ms 8908 KB Output is correct
6 Correct 7 ms 8780 KB Output is correct
7 Correct 9 ms 8780 KB Output is correct
8 Correct 6 ms 8780 KB Output is correct
9 Correct 6 ms 8780 KB Output is correct
10 Correct 9 ms 8776 KB Output is correct
11 Correct 7 ms 8780 KB Output is correct
12 Correct 7 ms 8776 KB Output is correct
13 Correct 7 ms 8848 KB Output is correct
14 Correct 7 ms 8780 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 29632 KB Output is correct
2 Correct 419 ms 29556 KB Output is correct
3 Correct 409 ms 29684 KB Output is correct
4 Correct 509 ms 33736 KB Output is correct
5 Correct 332 ms 32660 KB Output is correct
6 Correct 378 ms 42200 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8744 KB Output is correct
2 Correct 18 ms 8752 KB Output is correct
3 Correct 18 ms 8792 KB Output is correct
4 Correct 21 ms 8680 KB Output is correct
5 Correct 7 ms 8908 KB Output is correct
6 Correct 7 ms 8780 KB Output is correct
7 Correct 9 ms 8780 KB Output is correct
8 Correct 6 ms 8780 KB Output is correct
9 Correct 6 ms 8780 KB Output is correct
10 Correct 9 ms 8776 KB Output is correct
11 Correct 7 ms 8780 KB Output is correct
12 Correct 7 ms 8776 KB Output is correct
13 Correct 7 ms 8848 KB Output is correct
14 Correct 7 ms 8780 KB Output is correct
15 Correct 365 ms 29632 KB Output is correct
16 Correct 419 ms 29556 KB Output is correct
17 Correct 409 ms 29684 KB Output is correct
18 Correct 509 ms 33736 KB Output is correct
19 Correct 332 ms 32660 KB Output is correct
20 Correct 378 ms 42200 KB Output is correct
21 Correct 361 ms 30896 KB Output is correct
22 Correct 362 ms 30760 KB Output is correct
23 Correct 403 ms 30820 KB Output is correct
24 Correct 402 ms 33768 KB Output is correct
25 Correct 319 ms 39364 KB Output is correct
26 Correct 385 ms 30860 KB Output is correct
27 Correct 375 ms 30756 KB Output is correct
28 Correct 358 ms 30812 KB Output is correct
29 Correct 420 ms 34208 KB Output is correct
30 Correct 410 ms 36756 KB Output is correct
31 Correct 348 ms 30776 KB Output is correct
32 Correct 397 ms 30616 KB Output is correct
33 Correct 363 ms 30372 KB Output is correct
34 Correct 467 ms 33204 KB Output is correct
35 Correct 304 ms 38044 KB Output is correct
36 Correct 396 ms 31856 KB Output is correct