Submission #1279866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279866		swishy123	Valley (BOI19_valley)	C++20	100 / 100	471 ms	39656 KiB

valley

#include <bits/stdc++.h>

#define int long long
#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define x first
#define y second

const ll inf = 1e18;
const int def = 4e6+1;
using namespace std;

int st1[def], st2[def], lazy1[def], lazy2[def];
void push(int crr, int l, int r){
    st1[crr * 2 + 1] += lazy1[crr];
    st1[crr * 2 + 2] += lazy1[crr];

    st2[crr * 2 + 1] += lazy2[crr];
    st2[crr * 2 + 2] += lazy2[crr];

    lazy1[crr * 2 + 1] += lazy1[crr];
    lazy1[crr * 2 + 2] += lazy1[crr];

    lazy2[crr * 2 + 1] += lazy2[crr];
    lazy2[crr * 2 + 2] += lazy2[crr];

    lazy1[crr] = lazy2[crr] = 0;
}

void update1(int l, int r, int ql, int qr, int crr, int val){
    if (qr < l || ql > r)
        return;
    if (l >= ql && r <= qr){
        st1[crr] += val;
        lazy1[crr] += val;
        return;
    }
    push(crr, l, r);
    int mid = (l + r) / 2;

    update1(l, mid, ql, qr, crr * 2 + 1, val);
    update1(mid + 1, r, ql, qr, crr * 2 + 2, val);

    st1[crr] = min(st1[crr * 2 + 1], st1[crr * 2 + 2]);
    st2[crr] = min(st2[crr * 2 + 1], st2[crr * 2 + 2]);
}

void update2(int l, int r, int ql, int qr, int crr, int val){
    if (qr < l || ql > r)
        return;
    if (l >= ql && r <= qr){
        st2[crr] += val;
        lazy2[crr] += val;
        return;
    }
    push(crr, l, r);
    int mid = (l + r) / 2;

    update2(l, mid, ql, qr, crr * 2 + 1, val);
    update2(mid + 1, r, ql, qr, crr * 2 + 2, val);

    st1[crr] = min(st1[crr * 2 + 1], st1[crr * 2 + 2]);
    st2[crr] = min(st2[crr * 2 + 1], st2[crr * 2 + 2]);
}

int get1(int l, int r, int ql, int qr, int crr){
    if (qr < l || ql > r)
        return inf;
    if (l >= ql && r <= qr)
        return st1[crr];
    push(crr, l, r);
    int mid = (l + r) / 2;

    return min(get1(l, mid, ql, qr, crr * 2 + 1), get1(mid + 1, r, ql, qr, crr * 2 + 2));
}

int get2(int l, int r, int ql, int qr, int crr){
    if (qr < l || ql > r)
        return inf;
    if (l >= ql && r <= qr)
        return st2[crr];
    push(crr, l, r);
    int mid = (l + r) / 2;

    return min(get2(l, mid, ql, qr, crr * 2 + 1), get2(mid + 1, r, ql, qr, crr * 2 + 2));
}

void solve(){
    int n, s, q, e;
    cin >> n >> s >> q >> e;

    e--;
    vector<pi> E;
    vector<vector<pi>> edg(n);

    for (int i = 0; i < n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;

        u--; v--;
        edg[u].push_back({v, w});
        edg[v].push_back({u, w});

        E.push_back({u, v});
    }

    vector<int> in(n, 0), out(n, 0);
    int t = 0;

    auto dfs = [&](int u, int pre, auto&& dfs) -> void{
        in[u] = t++;
        for (auto [v, w] : edg[u]){
            if (v == pre)
                continue;
            dfs(v, u, dfs);
        }
        out[u] = t - 1;
    };
    dfs(0, -1, dfs);

    auto shop = vector<int>(n, 0);
    for (int i = 0; i < s; i++){
        int u;
        cin >> u;

        shop[u - 1] = 1;
    }

    auto dfs2 = [&](int u, int pre, int dis, auto&& dfs2) -> void{
        if (shop[u])
            update1(0, n - 1, in[u], in[u], 0, dis);
        else
            update1(0, n - 1, in[u], in[u], 0, inf);

        update2(0, n - 1, in[u], in[u], 0, dis);
        for (auto [v, w] : edg[u]){
            if (v == pre)
                continue;
            dfs2(v, u, dis + w, dfs2);
        }
    };
    dfs2(0, -1, 0, dfs2);

    vector<vector<pi>> qr(n);
    vector<bool> escaped = vector<bool>(    q, 0);

    for (int i = 0; i < q; i++){
        int x, u;
        cin >> x >> u;

        qr[u - 1].push_back({x - 1, i});
        auto [p1, p2] = E[x - 1];
        int p = p1;

        int dis1 = get2(0, n - 1, in[p1], in[p1], 0);
        int dis2 = get2(0, n - 1, in[p2], in[p2], 0);

        if (dis2 > dis1)
            p = p2;
        
        bool flag1 = (in[e] >= in[p]) && (in[e] <= out[p]);
        bool flag2 = (in[u - 1] >= in[p]) && (in[u - 1] <= out[p]);

        if (flag1 == flag2)
            escaped[i] = 1;
    }
    vector<int> res(q, inf);

    auto reroot = [&](int u, int pre, auto&& reroot) -> void{
        // cout << "Root = " << u << ": "; 
        // for (int i = 0; i < n; i++)
        //     cout << get2(0, n - 1, i, i, 0) << ' ';
        // cout << endl;

        for (auto [x, indx] : qr[u]){
            auto [p1, p2] = E[x];
            int p = p1;

            int dis1 = get2(0, n - 1, in[p1], in[p1], 0);
            int dis2 = get2(0, n - 1, in[p2], in[p2], 0);

            if (dis2 > dis1){
                p = p2;
                swap(p1, p2);
            }
            
            bool flag = (in[u] >= in[p]) && (in[u] <= out[p]);
            if (!flag){
                if (in[p] > 0)
                    res[indx] = min(res[indx], get1(0, n - 1, 0, in[p] - 1, 0));
                if (out[p] + 1 < n)
                    res[indx] = min(res[indx], get1(0, n - 1, out[p] + 1, n - 1, 0));
            }
            else{
                p = p2;
                res[indx] = get1(0, n - 1, in[p], out[p], 0);
            }
        }

        for (auto [v, w] : edg[u]){
            if (v == pre)
                continue;
            update1(0, n - 1, 0, n - 1, 0, w);
            update1(0, n - 1, in[v], out[v], 0, -2 * w);
 
            update2(0, n - 1, 0, n - 1, 0, w);
            update2(0, n - 1, in[v], out[v], 0, -2 * w);

            reroot(v, u, reroot);
            update1(0, n - 1, 0, n - 1, 0, -w);
            update1(0, n - 1, in[v], out[v], 0, 2 * w);

            update2(0, n - 1, 0, n - 1, 0, -w);
            update2(0, n - 1, in[v], out[v], 0, 2 * w);
        }
    };
    reroot(0, -1, reroot);

    for (int i = 0; i < q; i++){
        if (escaped[i]){
            cout << "escaped" << endl;
            continue;
        }
        if (res[i] > 1e15)
            cout << "oo" << endl;
        else
            cout << res[i] << endl;
    }
}   

/*
*/

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

    if (ifstream("input.txt").good()){
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout); 
    }

    int t;
    t = 1;
    
    while (t--){
        solve();
    }
}

Compilation message (stderr)

valley.cpp:235:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  235 | main(){
      | ^~~~
valley.cpp: In function 'int main()':
valley.cpp:240:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  240 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:241:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41