Submission #1104622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104622		TVSown	Valley (BOI19_valley)	C++17	100 / 100	318 ms	97096 KiB

valley

///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
const int N = 1e5 + 5, MAX = 1e9 + 5, MOD = 1e9 + 7;
int n, s, q, spe, TIME;
vector<pair<int, int> > adj[N];
int in[N], out[N], check[N], vt[N], cnt[N], l1[N], r1[N], l2[N], r2[N];
queue<int> pq[N];
long long g[N], ans[N];
void dfs(int u, int p){
    in[u] = ++TIME;
    vt[TIME] = u;
    if(check[u]) ++cnt[u];
    for(pair<int, int> edge : adj[u]){
        int v = edge.F, w = edge.S;
        if(v == p) continue;
        g[v] = g[u] + w;
        dfs(v, u);
        cnt[u] += cnt[v];
    }
    out[u] = TIME;
}

struct edge{
    int u, v;
} e[N];

int isChild(int u, int v){
    if(in[u] <= in[v] && out[u] >= out[v]) return 1;
    return 0;
}
long long st[4 * N], lz[4 * N];
void build(int id, int l, int r){
    if(l == r){
        if(check[vt[l]]) st[id] = g[vt[l]];
        else st[id] = 1e18;
        return;
    }
    int m = (l + r) / 2;
    build(2 * id, l, m);
    build(2 * id + 1, m + 1, r);
    st[id] = min(st[2 * id], st[2 * id + 1]);
}

void down(int id){
    st[2 * id] += lz[id];
    st[2 * id + 1] += lz[id];
    lz[2 * id] += lz[id];
    lz[2 * id + 1] += lz[id];

    lz[id] = 0;
}

void update(int id, int l, int r, int u, int v, int w){
    if(l > v || r < u) return;
    if(u <= l && r <= v){
        st[id] += w;
        lz[id] += w;
        return;
    }
    down(id);
    int m = (l + r) / 2;
    update(2 * id, l, m, u, v, w);
    update(2 * id + 1, m + 1, r, u, v, w);
    st[id] = min(st[2 * id], st[2 * id + 1]);
}

long long get(int id, int l, int r, int u, int v){
    if(l > v || r < u) return 1e18;
    if(u <= l && r <= v){
        return st[id];
    }
    down(id);
    int m = (l + r) / 2;
    return min(get(2 * id, l, m, u, v), get(2 * id + 1, m + 1, r, u, v));
}

void result(int u, int p, int c){
    update(1, 1, n, in[u], out[u], -c);
    update(1, 1, n, 1, in[u] - 1, c);
    update(1, 1, n, out[u] + 1, n, c);

    while(pq[u].size()){
        int id = pq[u].front();
        pq[u].pop();
        if(!l2[id]){
            ans[id] = get(1, 1, n, l1[id], r1[id]);
        }else{
            ans[id] = min(get(1, 1, n, l1[id], r1[id]), get(1, 1, n, l2[id], r2[id]));
        }
    }
    for(pair<int, int> edge : adj[u]){
        int v = edge.F, w = edge.S;
        if(v == p) continue;
        result(v, u, w);
    }

    update(1, 1, n, in[u], out[u], c);
    update(1, 1, n, 1, in[u] - 1, -c);
    update(1, 1, n, out[u] + 1, n, -c);
}

void solve(){
    cin >> n >> s >> q >> spe;
    for(int i = 1; i < n; ++i){
        int u, v, w; cin >> u >> v >> w;

        adj[u].pb({v, w});
        adj[v].pb({u, w});
        e[i] = {u, v};
    }
    for(int i = 1; i <= s; ++i){
        int u; cin >> u;
        check[u] = 1;
    }
    dfs(1, 0);
    build(1, 1, n);
    for(int i = 1; i <= q; ++i){
        int id, r; cin >> id >> r;

        int u = e[id].u, v = e[id].v;
        if(in[u] > in[v]) swap(u, v);
        if(isChild(v, r) == isChild(v, spe)){
            ans[i] = 1;
        }else{
            if(isChild(v, r)){
                if(cnt[v] == 0){
                    ans[i] = -1;
                }else{
                    l1[i] = in[v];
                    r1[i] = out[v];
                    pq[r].push(i);
                }

            }else{
                if(cnt[1] - cnt[v] == 0) ans[i] = -1;
                else{
                    l1[i] = 1;
                    r1[i] = in[v] - 1;
                    l2[i] = out[v] + 1;
                    r2[i] = n;
                    pq[r].push(i);
                }
            }
        }
    }
    result(1, 0, 0);
    for(int i = 1; i <= q; ++i){
        if(ans[i] == 1) cout << "escaped\n";
        else if(ans[i] == -1) cout << "oo\n";
        else cout << ans[i] << "\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    inp("in.txt");

    solve();
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:9:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
valley.cpp:165:5: note: in expansion of macro 'inp'
  165 |     inp("in.txt");
      |     ^~~

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