Submission #1006064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006064		pudelos	Valley (BOI19_valley)	C++17	36 / 100	3048 ms	20940 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define pi pair<int, int>
#define f first
#define s second
#define sz(A) (int)(A.size())
#define ll long long 
#define pb push_back
#define eb emplace_back
#define V vector
const int base=(1<<17);
const ll inf=1e16;
int n, s, q, e;
struct Edge { int v, u, c, idx; };
struct SegmentTree {
  ll T[2*base];
  void update(int a, int b, ll x) {
    if(a>b) return;
    FOR(i, a, b) T[i]+=x;
  }
  ll query(int a, int b) {
    if(a>b) return inf;
    ll res=inf;
    FOR(i, a, b) res=min(res, T[i]);
    return res;
  }
} AT;
V<V<Edge>> con;
V<int> pre, post, sajs;
V<V<pi>> todo;
V<ll> odl, odp;
V<Edge> edges;
V<bool> jest_sklepem;
int tpre=0, tpost=0;

void dfs1(int v, int p=0, ll d=0) {
  pre[v]=++tpre;
  sajs[v]=1;
  if(jest_sklepem[v]) AT.update(pre[v], pre[v], d);
  for(Edge kr : con[v]) {
    int u = kr.u;
    int c = kr.c;
    if(p==u) continue;
    dfs1(u, v, d+c);
    sajs[v]+=sajs[u];
  }
  post[v]=++tpost;
}

bool jest_ojcem(int a, int b) {
  return (pre[a]<=pre[b] && post[a]>=post[b]);
}

void dfs2(int v, int p=0) {
  for(auto &[idxkr, qidx] : todo[v]) {
    int a = edges[idxkr].v;
    int b = edges[idxkr].u;
    if(!jest_ojcem(a, b)) swap(a, b);

    int start = pre[b];
    int kon = pre[b]+sajs[b]-1;

    if(start<=pre[v] && pre[v]<=kon) {
      // zawiera sie w poddrzewie
      odp[qidx] = AT.query(start, kon);
    } else {
      odp[qidx] = min(AT.query(1, start-1), AT.query(kon+1, n));
    }
  }
  for(Edge kr : con[v]) {
    int u = kr.u;
    int c = kr.c;
    int idx = kr.idx;
    if(p==u) continue;
    // aktualizuj
    int start = pre[u];
    int kon = pre[u]+sajs[u]-1;
    AT.update(start, kon, -c);
    AT.update(1, start-1, c);
    AT.update(kon+1, n, c);
    dfs2(u, v);
    // cofnij aktualizacje
    AT.update(start, kon, c);
    AT.update(1, start-1, -c);
    AT.update(kon+1, n, -c);
  }
}

int main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> n >> s >> q >> e;
  con.resize(n+1);
  todo.resize(n+1);
  pre.resize(n+1);
  post.resize(n+1);
  odl.resize(n+1);
  edges.resize(n);
  odp.resize(q+1);
  jest_sklepem.resize(n+1);
  sajs.resize(n+1);
  int a, b, c;
  FOR(i, 1, n-1) {
    cin >> a >> b >> c;
    con[a].pb({a, b, c, i});
    con[b].pb({b, a, c, i});
    edges[i] = {a, b, c, i};
  }

  V<int> sklepy;
  AT.update(1, n, inf);
  FOR(i, 1, s) {
    cin>>a;
    if(jest_sklepem[a]) continue;
    jest_sklepem[a]=1;
    sklepy.eb(a);
  }

  // licz pre, post, AT.T(odl), sajs
  dfs1(e);

  for(int a : sklepy) {
    AT.update(pre[a], pre[a], -inf);
  }

  int id, v;
  FOR(i, 1, q) {
    cin >> id >> v;
    Edge kr = edges[id];
    int a = kr.v;
    int b = kr.u;
    // a wyzej
    if(!jest_ojcem(a, b)) swap(a, b);
    if(!(jest_ojcem(e, a) && jest_ojcem(b, v))) odp[i]=-1;
    else todo[v].pb({id, i});
  }

  dfs2(e);

  FOR(i, 1, q) {
    ll val = odp[i];
    if(val==-1) cout << "escaped\n";  
    else if(val>=1e14) cout << "oo\n";
    else cout << val << '\n';
  }
}

Compilation message (stderr)

valley.cpp: In function 'void dfs2(int, int)':
valley.cpp:74:9: warning: unused variable 'idx' [-Wunused-variable]
   74 |     int idx = kr.idx;
      |         ^~~

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