oj.uz

Submission #594106

# Submission time Handle Problem Language Result Execution time Memory
594106 2022-07-12T06:05:32 Z Do_you_copy Valley (BOI19_valley) C++17
100 / 100
 276 ms 57460 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll maxN = 2e5 + 1;
ll n, s, q, e;
ll cnt = 1;
ll a[maxN], pos[maxN], dis[maxN], rpos[maxN], child[maxN];
ll depth[maxN];
bool isshop[maxN];
vector <pii> adj[maxN];
ll st[maxN * 4];
pii edge[maxN];

void build(ll id = 1, ll l = 1, ll r = n){
    if (l == r){
        st[id] = isshop[rpos[l]] ? dis[rpos[l]] : inf;
        return;
    }
    ll mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = min(st[id * 2], st[id * 2 + 1]);
}

ll get(ll id, ll i, ll j, ll l = 1, ll r = n){
    if (r < i || l > j) return inf;
    if (i <= l && r <= j) return st[id];
    ll mid = (l + r) / 2;
    return min(get(id * 2, i, j, l, mid), get(id * 2 + 1, i, j, mid + 1, r));
}

void pre_dfs(ll u, ll p){
    pos[u] = cnt;
    rpos[cnt++] = u;
    depth[u] = depth[p] + 1;
    for (const pii &i: adj[u]){
        if (i.fi == p) continue;
        dis[i.fi] = dis[u] + i.se;
        pre_dfs(i.fi, u);
        child[u] += child[i.fi] + 1;
    }
}

pii stble[maxN][20];
void dfs(ll u, ll p){
    stble[u][0].fi = get(1, pos[u], pos[u] + child[u]);
    if (stble[u][0].fi != inf) stble[u][0].fi -= dis[u];
    stble[u][0].se = p;
    for (ll i = 1; i < 20; ++i){
        stble[u][i].fi = min(stble[u][i - 1].fi, stble[stble[u][i - 1].se][i - 1].fi + dis[u] - dis[stble[u][i - 1].se]);
        stble[u][i].se = stble[stble[u][i - 1].se][i - 1].se;
    }
    for (const pii &i: adj[u]){
        if (i.fi == p) continue;
        dfs(i.fi, u);
    }
}

ll findshop(ll u, ll v){
    ll k = depth[u] - depth[v];
    ll uu = u;
    ll ans = inf;
    for (ll i = 19; i >= 0; --i){
        if (depth[stble[u][i].se] >= depth[v] - 1){
            ans = min(ans, stble[u][i].fi + dis[uu] - dis[u]);
            u = stble[u][i].se;
        }
    }
    return ans;
}

void Init(){
    cin >> n >> s >> q >> e;
    for (ll i = 1; i < n; ++i){
        ll u, v, w;
        cin >> u >> v >> w;
        edge[i] = {u, v};
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    for (ll i = 1; i <= s; ++i){
        ll t; cin >> t;
        isshop[t] = 1;
    }
    for (ll i = 0; i <= n; ++i){
        for (ll j = 0; j < 20; ++j) stble[i][j] = {inf, 0};
    }
    pre_dfs(e, 0);
    build();
    dfs(e, 0);
    while (q--){
        ll i, r;
        cin >> i >> r;
        ll u, v;
        u = dis[edge[i].fi] < dis[edge[i].se] ? edge[i].fi : edge[i].se;
        v = u ^ edge[i].fi ^ edge[i].se;
        if (pos[r] < pos[v] || pos[r] > pos[v] + child[v]){
            cout << "escaped\n";
        }
        else{
            ll tem = findshop(r, v);
            if (tem >= inf) cout << "oo\n";
            else cout << tem << "\n";
        }
    }
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

valley.cpp: In function 'll findshop(ll, ll)':
valley.cpp:84:8: warning: unused variable 'k' [-Wunused-variable]
   84 |     ll k = depth[u] - depth[v];
      |        ^
valley.cpp: In function 'int main()':
valley.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5204 KB Output is correct
2 Correct 5 ms 5204 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5176 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5204 KB Output is correct
2 Correct 5 ms 5204 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5176 KB Output is correct
5 Correct 5 ms 5560 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 5 ms 5460 KB Output is correct
10 Correct 4 ms 5516 KB Output is correct
11 Correct 4 ms 5460 KB Output is correct
12 Correct 5 ms 5564 KB Output is correct
13 Correct 4 ms 5500 KB Output is correct
14 Correct 4 ms 5460 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 50700 KB Output is correct
2 Correct 212 ms 53452 KB Output is correct
3 Correct 208 ms 53612 KB Output is correct
4 Correct 246 ms 55116 KB Output is correct
5 Correct 223 ms 55372 KB Output is correct
6 Correct 276 ms 57020 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5204 KB Output is correct
2 Correct 5 ms 5204 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5176 KB Output is correct
5 Correct 5 ms 5560 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 5 ms 5460 KB Output is correct
10 Correct 4 ms 5516 KB Output is correct
11 Correct 4 ms 5460 KB Output is correct
12 Correct 5 ms 5564 KB Output is correct
13 Correct 4 ms 5500 KB Output is correct
14 Correct 4 ms 5460 KB Output is correct
15 Correct 176 ms 50700 KB Output is correct
16 Correct 212 ms 53452 KB Output is correct
17 Correct 208 ms 53612 KB Output is correct
18 Correct 246 ms 55116 KB Output is correct
19 Correct 223 ms 55372 KB Output is correct
20 Correct 276 ms 57020 KB Output is correct
21 Correct 166 ms 52944 KB Output is correct
22 Correct 211 ms 52820 KB Output is correct
23 Correct 199 ms 52968 KB Output is correct
24 Correct 263 ms 54868 KB Output is correct
25 Correct 239 ms 57460 KB Output is correct
26 Correct 167 ms 53068 KB Output is correct
27 Correct 189 ms 52924 KB Output is correct
28 Correct 197 ms 53192 KB Output is correct
29 Correct 247 ms 54276 KB Output is correct
30 Correct 270 ms 55740 KB Output is correct
31 Correct 188 ms 53188 KB Output is correct
32 Correct 203 ms 52940 KB Output is correct
33 Correct 232 ms 53312 KB Output is correct
34 Correct 250 ms 54800 KB Output is correct
35 Correct 239 ms 57136 KB Output is correct
36 Correct 227 ms 54736 KB Output is correct