oj.uz

Submission #936963

# Submission time Handle Problem Language Result Execution time Memory
936963 2024-03-03T06:29:06 Z VinhLuu Valley (BOI19_valley) C++17
100 / 100
 234 ms 57680 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e5 + 5;
const int oo = 1e16;
const int mod = 1e9 + 7;

int n, s, q, e, X[N], Y[N], W[N];
bool fl[N];
vector<pii> p[N], Q[N];

struct ST{
    int T[N << 2], lz[N << 2];
    void dolz(int i){
        if(lz[i] == 0) return;
        int x = lz[i];
        lz[i] = 0;
        T[i << 1] += x;
        T[i << 1|1] += x;
        lz[i << 1] += x;
        lz[i << 1|1] += x;
    }
    void update(int i,int l,int r,int u,int v,int x){
        if(l > v || r < u || l > r) return;
        if(u <= l && r <= v){
            T[i] += x;
            lz[i] += x;
            return;
        }
        dolz(i);
        int mid = (l + r) >> 1;
        update(i << 1, l, mid, u, v, x);
        update(i << 1|1, mid + 1, r, u, v, x);
        T[i] = min(T[i << 1], T[i << 1|1]);
    }
    int get(int i,int l,int r,int u,int v){
        if(l > v || r < u ||l > r) return oo;
        if(u <= l && r <= v) return T[i];
        int mid = (l + r) >> 1;
        dolz(i);
        return min(get(i << 1, l, mid, u, v), get(i << 1|1, mid + 1, r, u, v));
    }
} st;

namespace AC{
    int in[N], demin, en[N], d[N], kq[N], f[N][22];
    void pre(int u,int v){
        in[u] = ++demin;
        if(u == 1) for(int i = 0; i <= 20; i ++) f[u][i] = u;
        else{
            f[u][0] = v;
            for(int i = 1; i <= 20; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
        }
        for(auto [j, w] : p[u]){
            if(j == v) continue;
            d[j] = d[u] + w;
            pre(j, u);
        }
        en[u] = demin;
    }

    bool kt(int u,int v){
        return in[u] <= in[v] && in[v] <= en[u];
    }

    int cal(int x,int y){
        int lca = x;
        if(!kt(x, y)){
            int h = x;
            for(int i = 20; i >= 0; i --){
                if(kt(f[h][i], y)) lca = f[h][i];
                else h = f[h][i];
            }
        }
        return d[x] + d[y] - 2 * d[lca];
    }

    void dfs(int u,int v){
        for(auto [id, j] : Q[u]){
            int x = X[j], y = Y[j];
            if(in[x] > in[y]) swap(x, y);
            if(kt(y, u)){
                if(kt(y, e)) kq[id] = -1;
                else kq[id] = st.get(1, 1, n, in[y], en[y]);
            }else{
//                cout << u << " " << id << " " << j << "h\n";
//                for(int i = 1; i <= n; i ++) cout << i << " " << st.get(1, 1, n, in[i], in[i]) << "\n";

                if(!kt(y, e)) kq[id] = -1;
                else kq[id] = min(st.get(1, 1, n, 1, in[y] - 1), st.get(1, 1, n, en[y] + 1, n));
            }
        }
        for(auto [j, w] : p[u]){
            if(j == v) continue;
            st.update(1, 1, n, 1, n, w);
            st.update(1, 1, n, in[j], en[j], -2 * w);
            dfs(j, u);
            st.update(1, 1, n, 1, n, -w);
            st.update(1, 1, n, in[j], en[j], 2 * w);
        }
    }
    void solve(){
        pre(1, 0);
        for(int i = 1; i <= n; i ++){
            if(fl[i]) st.update(1, 1, n, in[i], in[i], d[i]);
            else st.update(1, 1, n, in[i], in[i], oo);
        }
        dfs(1, 0);
        for(int i = 1; i <= q; i ++){
            if(kq[i] == -1) cout << "escaped\n";
            else if(kq[i] >= (int)1e14) cout << "oo\n";
            else cout << kq[i] << "\n";
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n >> s >> q >> e;
    fl[e] = true;
    for(int i = 1; i < n; i ++){
        cin >> X[i] >> Y[i] >> W[i];
        p[X[i]].pb({Y[i], W[i]});
        p[Y[i]].pb({X[i], W[i]});
    }
    for(int i = 1; i <= s; i ++){
        int x; cin >> x; fl[x] = true;
    }
    for(int i = 1; i <= q; i ++){
        int j, r; cin >> j >> r;
        Q[r].pb({i, j});
    }
    AC :: solve();
}

Compilation message

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(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Output is correct
2 Correct 3 ms 9208 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Output is correct
2 Correct 3 ms 9208 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 4 ms 11096 KB Output is correct
7 Correct 4 ms 11100 KB Output is correct
8 Correct 3 ms 11100 KB Output is correct
9 Correct 3 ms 11100 KB Output is correct
10 Correct 3 ms 11100 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 3 ms 10944 KB Output is correct
13 Correct 3 ms 11100 KB Output is correct
14 Correct 3 ms 11016 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 45592 KB Output is correct
2 Correct 201 ms 45908 KB Output is correct
3 Correct 190 ms 45488 KB Output is correct
4 Correct 222 ms 49416 KB Output is correct
5 Correct 201 ms 48980 KB Output is correct
6 Correct 234 ms 57680 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Output is correct
2 Correct 3 ms 9208 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 4 ms 11096 KB Output is correct
7 Correct 4 ms 11100 KB Output is correct
8 Correct 3 ms 11100 KB Output is correct
9 Correct 3 ms 11100 KB Output is correct
10 Correct 3 ms 11100 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 3 ms 10944 KB Output is correct
13 Correct 3 ms 11100 KB Output is correct
14 Correct 3 ms 11016 KB Output is correct
15 Correct 183 ms 45592 KB Output is correct
16 Correct 201 ms 45908 KB Output is correct
17 Correct 190 ms 45488 KB Output is correct
18 Correct 222 ms 49416 KB Output is correct
19 Correct 201 ms 48980 KB Output is correct
20 Correct 234 ms 57680 KB Output is correct
21 Correct 173 ms 45076 KB Output is correct
22 Correct 187 ms 45020 KB Output is correct
23 Correct 181 ms 44884 KB Output is correct
24 Correct 218 ms 47656 KB Output is correct
25 Correct 221 ms 55000 KB Output is correct
26 Correct 169 ms 45140 KB Output is correct
27 Correct 178 ms 44948 KB Output is correct
28 Correct 184 ms 45144 KB Output is correct
29 Correct 203 ms 48464 KB Output is correct
30 Correct 214 ms 52536 KB Output is correct
31 Correct 168 ms 45244 KB Output is correct
32 Correct 187 ms 45140 KB Output is correct
33 Correct 205 ms 45284 KB Output is correct
34 Correct 212 ms 47956 KB Output is correct
35 Correct 205 ms 53592 KB Output is correct
36 Correct 200 ms 49196 KB Output is correct