Submission #1006067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006067		pudelos	Valley (BOI19_valley)	C++17	100 / 100	343 ms	29836 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;

struct SegmentTree {
  ll tree[2*base], tree2[2*base];

  void push(int v) {
    int ls = 2*v;
    int rs = 2*v+1;
    
    tree2[ls] += tree2[v];
    tree2[rs] += tree2[v];
    tree[rs] += tree2[v];
    tree[ls] += tree2[v];
    tree2[v]=0;
  }

  ll query(int a, int b, int v=1, int l=0, int r=base-1) {
    if(a>b) return inf;
    if(a<=l && r<=b) return tree[v];
    if(r<a || b<l) return inf;
    int mid = l+(r-l)/2;
    push(v);
    return min(query(a, b, 2*v, l, mid), query(a, b, 2*v+1, mid+1, r));
  }

  void update(int a, int b, ll x, int v=1, int l=0, int r=base-1) {
    if(a>b) return;
    if(r<a || b<l) return;
    if(a<=l && r<=b) {
      tree[v] += x;
      tree2[v] += x;
      return;
    }
    int mid = l+(r-l)/2;
    push(v);
    update(a, b, x, 2*v, l, mid);
    update(a, b, x, 2*v+1, mid+1, r);
    tree[v] = min(tree[2*v], tree[2*v+1]); 
  }
} 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:114:9: warning: unused variable 'idx' [-Wunused-variable]
  114 |     int idx = kr.idx;
      |         ^~~

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