oj.uz

Submission #496352

# Submission time Handle Problem Language Result Execution time Memory
496352 2021-12-21T06:16:56 Z xynex Valley (BOI19_valley) C++17
100 / 100
 528 ms 183760 KB 
/*
* Author: xynex
* Created: 21.12.2021 11:20
* Why am I so stupid? :c
* Slishkom slab
*/

#include <bits/stdc++.h>

// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse,-fgcse-lm")
// #pragma GCC optimize("-ftree-pre,-ftree-vrp")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define ll long long
#define dl double long
#define ull unsigned long long
#define pr pair
#define vt vector
#define ff first
#define ss second
#define mp make_pair
#define sz(a) (int)a.size()
#define pb push_back
#define pf push_front
#define popB pop_back
#define popF pop_front
#define bit_count __builtin_popcount
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed << setprecision(x)

template<typename T> T get_rand(T l, T r) {
    random_device rd;
    mt19937 gen(rd());
    return uniform_int_distribution<T>(l, r)(gen);
}

template<typename T> T lcm(T a, T b) { return a * (b / __gcd(a, b)); }

template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(array<A, S>& a);
template<class T> void read(T& x) { cin >> x; }
void read(double& d) { string t; read(t); d = stod(t); }
void read(long double& d) { string t; read(t); d = stold(t); }
template<class H, class... T> void read(H& h, T&... t) { read(h); read(t...); }
template<class A> void read(vt<A>& x) { for (auto& a : x) read(a); }
template<class A, size_t S> void read(array<A, S>& x) { for (auto& a : x) read(a); }

string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return string(s); }
string to_string(string s) { return s; }
string to_string(vt<bool> v) { string res; for (int i = 0; i < sz(v); ++i) res += char('0' + v[i]); return res; }
template<size_t S> string to_string(bitset<S> b) { string res; for (int i = 0; i < S; ++i) res += char('0' + b[i]); return res; }
template<class T> string to_string(T v) { bool f = 1; string res; for (auto x : v) { if (!f) res += ' '; f = 0; res += to_string(x); } return res; }

template<class A> void write(A x) { cout << to_string(x); }
template<class H, class... T> void write(const H& h, const T&... t) { write(h); write(t...); }

void print() { write("\n"); }
template<class H, class... T> void print(const H& h, const T&... t) { write(h); if (sizeof...(t)) write(' '); print(t...); }

void freop(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int MOD = 1e9 + 7;
const int N = 3e6 + 5;
const ll INF = 9e18;
const int M = 3e3 + 5;
const dl pi = acos(-1);
const dl eps = 1e-12;
const int sq = 700;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
/* ll vs int*/

void precalc() {

}

int tin[N], tout[N], timer = 0, up[N][30], LOG, n, s, q, e;
ll dist[N], depth[N], pos[N], mn[N], add[N], ans[N];
vt<pr<int, ll> > g[N], query[N];
pr<int, pr<int, int>> all[N];
bool shop[N];
void dfs(int v, int p) {
    tin[v] = ++timer;
    pos[timer] = v;
    up[v][0] = p;
    for(int i = 1; i <= LOG; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
    for(auto to : g[v]) {
        if(to.ff == p) continue;
        dist[to.ff] = dist[v] + to.ss;
        dfs(to.ff, v);
    }
    tout[v] = timer;
}

bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	if(upper(a, b)) return a;
	if(upper(b, a)) return b;
	for(int i = LOG; i >= 0; --i) {
		if(!upper(up[a][i], b)) a = up[a][i];
	}
	return up[a][0];
}
ll get_dist(int a, int b) {
    return dist[a] + dist[b] - dist[lca(a, b)] * 2;
}

void build(int l = 1, int r = n, int v = 1) {
    if(l == r) {
        mn[v] = INF;
        if(shop[pos[l]]) mn[v] = dist[pos[l]];
        return;
    }
    int mid = (r + l) >> 1;
    build(l, mid, v * 2); build(mid + 1, r, v * 2 + 1);
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}
void lazy(int tl, int tr, int v) {
    if(tl != tr) {
        add[v * 2] += add[v];
        add[v * 2 + 1] += add[v];
    }
    mn[v] += add[v];
    add[v] = 0;
}
void upd(int l, int r, ll ind, int tl = 1, int tr = n, int v = 1) {
    lazy(tl, tr, v);
    if(tl > r || tr < l) return;
    if(tl >= l && tr <= r) {
        add[v] += ind;
        lazy(tl, tr, v);
        return;
    }
    int mid = (tl + tr) >> 1;
    upd(l, r, ind, tl, mid, v * 2); upd(l, r, ind, mid + 1, tr, v * 2 + 1);
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}
ll get(int l, int r, int tl = 1, int tr = n, int v = 1) {
    lazy(tl, tr, v);
    if(tl > r || tr < l) return INF;
    if(tl >= l && tr <= r) return mn[v];
    int mid = (tl + tr) >> 1;
    return min(get(l, r, tl, mid, v * 2), get(l, r, mid + 1, tr, v * 2 + 1));
}
void go(int v, int p) {
   // print(v);
    for(auto to : query[v]) {
        int edge = to.ff;
        int pq = to.ss;
        int x = all[edge].ss.ff, y = all[edge].ss.ss, weight = all[edge].ff;
        //print(x, y, weight, get_dist(y, e), get_dist(x, v), get_dist(v, e));
        if((weight + get_dist(y, e) + get_dist(x, v)) == get_dist(v, e)) ans[pq] = get(tin[x], tout[x]);
        else if((weight + get_dist(x, e) + get_dist(y, v)) == get_dist(v, e)) ans[pq] = get(tin[y], tout[y]);
        else ans[pq] = -1;
    }
    for(auto to: g[v]) {
        if(to.ff == p) continue;
        upd(tin[to.ff], tout[to.ff], -to.ss);
        upd(1, tin[to.ff] - 1, to.ss);
        upd(tout[to.ff] + 1, n, to.ss);
        go(to.ff, v);
        upd(tin[to.ff], tout[to.ff], to.ss);
        upd(1, tin[to.ff] - 1, -to.ss);
        upd(tout[to.ff] + 1, n, -to.ss);
    }
}
void solve() {
    read(n, s, q, e);
    LOG = ceil(log2(n));
    for(int i = 0; i <= LOG; ++i) {
        for(int j = 1; j <= n; ++j) up[j][i] = -1;
    }
    int id = 1;
    for(int i = 1; i < n; ++i) {
        int l, r, w; read(l, r, w);
        all[id++] = {w, {l, r}};
        g[l].pb({r, w});
        g[r].pb({l, w});
    }
    for(int i = 1; i <= s; ++i) {
        int whr; read(whr);
        shop[whr] = 1;
    }
    for(int i = 1; i <= q; ++i) {
        int x, y; read(x, y);
        query[y].pb({x, i});
    }
    dfs(e, e);
    build();
    go(e, e);
    for(int i = 1; i <= q; ++i) {
        if(ans[i] > 1e14) print("oo");
        else if(ans[i] != -1) print(ans[i]);
        else print("escaped");
    }
}

int main() {
    //freop("");
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //read(t);
    precalc();
    for (int i = 1; i <= t; ++i) {
        //write("Case #" + to_string(i) + ": ");
        solve();
    }
    return 0;
}

Compilation message

valley.cpp: In function 'void freop(std::string)':
valley.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 141676 KB Output is correct
2 Correct 71 ms 141724 KB Output is correct
3 Correct 71 ms 141628 KB Output is correct
4 Correct 71 ms 141640 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 141676 KB Output is correct
2 Correct 71 ms 141724 KB Output is correct
3 Correct 71 ms 141628 KB Output is correct
4 Correct 71 ms 141640 KB Output is correct
5 Correct 81 ms 141516 KB Output is correct
6 Correct 75 ms 141552 KB Output is correct
7 Correct 68 ms 141480 KB Output is correct
8 Correct 72 ms 141504 KB Output is correct
9 Correct 79 ms 141544 KB Output is correct
10 Correct 67 ms 141472 KB Output is correct
11 Correct 67 ms 141472 KB Output is correct
12 Correct 83 ms 141508 KB Output is correct
13 Correct 70 ms 141508 KB Output is correct
14 Correct 77 ms 141536 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 169952 KB Output is correct
2 Correct 437 ms 169740 KB Output is correct
3 Correct 488 ms 169812 KB Output is correct
4 Correct 492 ms 173836 KB Output is correct
5 Correct 434 ms 173840 KB Output is correct
6 Correct 484 ms 179012 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 141676 KB Output is correct
2 Correct 71 ms 141724 KB Output is correct
3 Correct 71 ms 141628 KB Output is correct
4 Correct 71 ms 141640 KB Output is correct
5 Correct 81 ms 141516 KB Output is correct
6 Correct 75 ms 141552 KB Output is correct
7 Correct 68 ms 141480 KB Output is correct
8 Correct 72 ms 141504 KB Output is correct
9 Correct 79 ms 141544 KB Output is correct
10 Correct 67 ms 141472 KB Output is correct
11 Correct 67 ms 141472 KB Output is correct
12 Correct 83 ms 141508 KB Output is correct
13 Correct 70 ms 141508 KB Output is correct
14 Correct 77 ms 141536 KB Output is correct
15 Correct 406 ms 169952 KB Output is correct
16 Correct 437 ms 169740 KB Output is correct
17 Correct 488 ms 169812 KB Output is correct
18 Correct 492 ms 173836 KB Output is correct
19 Correct 434 ms 173840 KB Output is correct
20 Correct 484 ms 179012 KB Output is correct
21 Correct 409 ms 169944 KB Output is correct
22 Correct 428 ms 169708 KB Output is correct
23 Correct 480 ms 169736 KB Output is correct
24 Correct 483 ms 174448 KB Output is correct
25 Correct 460 ms 180644 KB Output is correct
26 Correct 446 ms 170052 KB Output is correct
27 Correct 502 ms 169784 KB Output is correct
28 Correct 424 ms 169816 KB Output is correct
29 Correct 457 ms 172808 KB Output is correct
30 Correct 470 ms 176328 KB Output is correct
31 Correct 449 ms 171040 KB Output is correct
32 Correct 457 ms 173132 KB Output is correct
33 Correct 480 ms 173284 KB Output is correct
34 Correct 516 ms 177212 KB Output is correct
35 Correct 528 ms 183760 KB Output is correct
36 Correct 476 ms 177464 KB Output is correct