Submission #936963

#	Time	Username	Problem	Language	Result	Execution time	Memory
936963		VinhLuu	Valley (BOI19_valley)	C++17	100 / 100	234 ms	57680 KiB

valley

//#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 (stderr)

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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41