oj.uz

Submission #893839

# Submission time Handle Problem Language Result Execution time Memory
893839 2023-12-27T14:17:02 Z kigash Valley (BOI19_valley) C++17
100 / 100
 179 ms 66900 KB 
#include "bits/stdc++.h"
using namespace std;       

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using ll = long long;
using ld = long double;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
void IOIGold2024_InshAllah() { ios_base::sync_with_stdio(false); cin.tie(NULL); }
ll binmul(ll a, ll b, ll c) { ll res = 0; while(b) { if(b&1) (res += a) %= c; (a += a) %= c; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll c) { ll res = 1; while(b) { if(b&1) (res *= a) %= c; (a *= a) %= c; b >>= 1; } return res; }
template<typename T> T gcd(T a, T b) { if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b) { return a/gcd(a, b)*b; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ld rnd() { return rng()%INT_MAX*1.0/INT_MAX; }

const ll inf = 1e18+7, MX = LLONG_MAX, MN = LLONG_MIN;
const ll mod = 1e9+7, N = 3e5+5;
vector<pair<ll, ll>> g[N];
ll d[N], dist[N], dp[N], up[N][20], t[N][20], tin[N], tout[N], timer;
pair<ll, ll> edge[N];

void dfs(ll v, ll p) {
    tin[v] = ++timer;
    up[v][0] = p, dist[v] = dist[p]+1;
    for(ll i=1; i<20; i++) up[v][i] = up[up[v][i-1]][i-1];
    for(auto [to, w]: g[v]) {
        if(to==p) continue;
        d[to] = d[v]+w;
        dfs(to, v);
        dp[v] = min(dp[v], dp[to]+w);
    }
    tout[v] = ++timer;
}

void qfs(ll v, ll p) {
    t[v][0] = dp[v]-d[v];
    for(ll i=1; i<20; i++) t[v][i] = min(t[v][i-1], t[up[v][i-1]][i-1]);
    for(auto [to, w]: g[v]) {
        if(to==p) continue;
        qfs(to, v);
    }
}

void kigash() {
    ll n, m, q, x;
    cin>>n>>m>>q>>x;
    for(ll i=1; i<n; i++) {
        ll u, v, w;
        cin>>u>>v>>w;
        edge[i] = {u, v};
        g[u].pb({v, w}), g[v].pb({u, w});
    }
    for(ll i=1; i<=n; i++) dp[i] = inf;
    for(ll i=1; i<=m; i++) {
        ll v;
        cin>>v;
        dp[v] = 0;
    }
    dfs(x, 0), qfs(x, 0);
    while(q--) {
        ll a, b;
        cin>>a>>b;
        ll u = edge[a].ff, v = edge[a].ss;
        if(dist[u]>dist[v]) swap(u, v);
        if(tin[v]<=tin[b] && tout[b]<=tout[v]) {
            ll k = dist[b]-dist[v], b_ = b, mn = inf;
            for(ll i=19; i>=0; i--) {
                if(k&(1<<i)) {
                    mn = min(mn, t[b][i]);
                    b = up[b][i];
                }
            }
            mn = min(mn, t[v][0]);
            if(mn+d[b_]>=inf) cout<<"oo\n";
            else cout<<mn+d[b_]<<"\n";
        }
        else cout<<"escaped\n";
    }
    return;
}

signed main(/*Kigash Amir*/) {
    // freopen("");
    IOIGold2024_InshAllah();
    ll tt = 1;
    // cin>>tt;
    for(ll i=1; i<=tt; i++) {
        kigash();
    }
}

Compilation message

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17244 KB Output is correct
2 Correct 4 ms 17240 KB Output is correct
3 Correct 5 ms 17276 KB Output is correct
4 Correct 5 ms 17240 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17244 KB Output is correct
2 Correct 4 ms 17240 KB Output is correct
3 Correct 5 ms 17276 KB Output is correct
4 Correct 5 ms 17240 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct
6 Correct 3 ms 17300 KB Output is correct
7 Correct 3 ms 17240 KB Output is correct
8 Correct 3 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 3 ms 17228 KB Output is correct
11 Correct 4 ms 17244 KB Output is correct
12 Correct 4 ms 17244 KB Output is correct
13 Correct 4 ms 17244 KB Output is correct
14 Correct 3 ms 17244 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 62308 KB Output is correct
2 Correct 142 ms 62208 KB Output is correct
3 Correct 143 ms 62288 KB Output is correct
4 Correct 162 ms 64340 KB Output is correct
5 Correct 151 ms 64340 KB Output is correct
6 Correct 179 ms 66388 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17244 KB Output is correct
2 Correct 4 ms 17240 KB Output is correct
3 Correct 5 ms 17276 KB Output is correct
4 Correct 5 ms 17240 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct
6 Correct 3 ms 17300 KB Output is correct
7 Correct 3 ms 17240 KB Output is correct
8 Correct 3 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 3 ms 17228 KB Output is correct
11 Correct 4 ms 17244 KB Output is correct
12 Correct 4 ms 17244 KB Output is correct
13 Correct 4 ms 17244 KB Output is correct
14 Correct 3 ms 17244 KB Output is correct
15 Correct 122 ms 62308 KB Output is correct
16 Correct 142 ms 62208 KB Output is correct
17 Correct 143 ms 62288 KB Output is correct
18 Correct 162 ms 64340 KB Output is correct
19 Correct 151 ms 64340 KB Output is correct
20 Correct 179 ms 66388 KB Output is correct
21 Correct 123 ms 62072 KB Output is correct
22 Correct 135 ms 61684 KB Output is correct
23 Correct 139 ms 61772 KB Output is correct
24 Correct 157 ms 63820 KB Output is correct
25 Correct 169 ms 66900 KB Output is correct
26 Correct 116 ms 61836 KB Output is correct
27 Correct 124 ms 61520 KB Output is correct
28 Correct 146 ms 61820 KB Output is correct
29 Correct 155 ms 63352 KB Output is correct
30 Correct 176 ms 64852 KB Output is correct
31 Correct 115 ms 61776 KB Output is correct
32 Correct 127 ms 61780 KB Output is correct
33 Correct 141 ms 62236 KB Output is correct
34 Correct 157 ms 63828 KB Output is correct
35 Correct 160 ms 66692 KB Output is correct
36 Correct 176 ms 63836 KB Output is correct