QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#806208#9862. Antivirusucup-team135RE 0ms0kbC++2310.5kb2024-12-08 23:39:242024-12-08 23:39:25

Judging History

This is the latest submission verdict.

  • [2024-12-08 23:39:25]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-12-08 23:39:24]
  • Submitted

answer

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
#include <array>
#include <functional>
#include <stack>
#include <memory>

using namespace std;

#define int long long
#define app push_back
#define all(x) x.begin(), x.end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl; }(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do { cout << #v << ": "; for (auto x : v) cout << x << ' '; cout << endl; } while(0)
#else
#define debug(...)
#define debugv(v)
#endif

struct DominatorTree{
    struct DSU{
        struct Vert{
            int p;
            pair<int, int> val;
        };

        vector<Vert> t;
        vector<int> ord;

        DSU(vector<int> &ord): ord(ord) { t.resize(ord.size()); for (int i = 0; i < ord.size(); i++) t[i].p = i; }

        int get(int v){
                if (t[v].p == v) return v;
                int new_p = get(t[v].p);
                if (ord[t[v].val.first] > ord[t[t[v].p].val.first]) t[v].val = t[t[v].p].val;
                t[v].p = new_p;
                return t[v].p;
        }

        void merge(int a, int b){
            a = get(a); b = get(b);
            if (a != b){
                t[b].p = a;
            }
        }

        int setVal(int v, pair<int, int> val){
            t[v].val = val;
        }

        pair<int, int> getVal(int v){
            get(v);
            return t[v].val;
        }
    };

    vector<vector<int> > g, gr, lg;
    vector<int> idom, sdom, was, tin;

    int timer;
    void dfs(int v){
        tin[v] = timer++;
        was[v] = 1;
        for (int to : g[v]) if (!was[to]) dfs(to);
    }

    vector<vector<int> > req;

    DominatorTree(int n, vector<pair<int, int> > &edges, int root){
        g.resize(n); gr.resize(n); lg.resize(n);
        idom.resize(n, -1); sdom.resize(n);
        was.resize(n, 0), tin.resize(n);
        req.resize(n);
        for (auto &&e : edges){
            g[e.first].push_back(e.second);
            gr[e.second].push_back(e.first);
        }
        timer = 0; dfs(root);
        vector<int> ord;
        for (int i = 0; i < n; i++) ord.push_back(i);
        sort(ord.begin(), ord.end(), [this](int w1, int w2){ return tin[w1] > tin[w2]; });
        DSU dsu(tin);
        for (int v : ord){
            sdom[v] = v;
            for (int to : gr[v]){
                if (v == to) continue;
                int val = tin[to] < tin[v] ? to : dsu.getVal(to).first;
                if (tin[val] < tin[sdom[v]]) sdom[v] = val;
            }

            req[sdom[v]].push_back(v);
            for (auto &&r : req[v]){
                auto val = dsu.getVal(r);
                if (tin[val.first] < tin[sdom[r]]){
                    lg[val.second].push_back(r);
                } else {
                    idom[r] = sdom[r];
                }
            }

            dsu.setVal(v, make_pair(sdom[v], v));
            for (int to : g[v]){
                if (tin[to] > tin[v] && dsu.t[to].p == to){
                    dsu.merge(v, to);
                }
            }
        }

        for (int i = 0; i < n; i++) was[i] = 0;

        for (int i = 0; i < n; i++) if (!was[i] && idom[i] != -1){
            vector<int> st;
            st.push_back(i);
            was[i] = 1;
            while(st.size()){
                int v = st.back(); st.pop_back();
                idom[v] = idom[i];
                for (int to : lg[v]) if (!was[to]) was[to] = 1, st.push_back(to);
            }
        }
    }
};



#ifdef LOCAL
int __lg(int x) { return 63 - __builtin_clzll(x); }
#endif

template<typename Data, typename Mod, typename UniteData, typename UniteMod, typename Apply>
struct MassSegmentTree {
  int h, n;
  Data zd;
  Mod zm;
  vector<Data> data;
  vector<Mod> mod;

  UniteData ud; // Data (Data, Data)
  UniteMod um; // Mod (Mod, Mod);
  Apply a; // Data (Data, Mod, int); last argument is the length of current segment (could be used for range += and sum counting, for instance)

  template<typename I>
  MassSegmentTree(int sz, Data zd, Mod zm, UniteData ud, UniteMod um, Apply a, I init) : h(__lg(sz) + 1), n(1 << h), zm(zm), zd(zd), data(2 * n, zd), mod(n, zm), ud(ud), um(um), a(a) {
    for (int i = 0; i < sz; ++i) data[i + n] = init(i);
    for (int i = n - 1; i > 0; --i) data[i] = ud(data[2 * i], data[2 * i + 1]);
  }

  MassSegmentTree(int sz, Data zd, Mod zm, UniteData ud, UniteMod um, Apply a) : h(__lg(sz) + 1), n(1 << h), zm(zm), zd(zd), data(2 * n, zd), mod(n, zm), ud(ud), um(um), a(a) {}

  void push(int i) {
    if (mod[i] == zm) return;
    apply(2 * i, mod[i]);
    apply(2 * i + 1, mod[i]);
    mod[i] = zm;
  }

  // is used only for apply
  int length(int i) { return 1 << (h - __lg(i)); }

  // used only for descent
  int left(int i) {
    int lvl = __lg(i);
    return (i & ((1 << lvl) - 1)) * (1 << (h - lvl));
  }

  // used only for descent
  int right(int i) {
    int lvl = __lg(i);
    return ((i & ((1 << lvl) - 1)) + 1) * (1 << (h - lvl));
  }

  template<typename S>
  void apply(int i, S x) {
    data[i] = a(data[i], x, length(i));
    if (i < n) mod[i] = um(mod[i], x);
  }

  void update(int i) {
    if (mod[i] != zm) return;
    data[i] = ud(data[2 * i], data[2 * i + 1]);
  }

  template<typename S>
  void update(int l, int r, S x) { // [l; r)
    l += n, r += n;
    for (int shift = h; shift > 0; --shift) {
      push(l >> shift);
      push((r - 1) >> shift);
    }
    for (int lf = l, rg = r; lf < rg; lf /= 2, rg /= 2) {
      if (lf & 1) apply(lf++, x);
      if (rg & 1) apply(--rg, x);
    }
    for (int shift = 1; shift <= h; ++shift) {
      update(l >> shift);
      update((r - 1) >> shift);
    }
  }

  Data get(int l, int r) { // [l; r)
    l += n, r += n;
    for (int shift = h; shift > 0; --shift) {
      push(l >> shift);
      push((r - 1) >> shift);
    }
    Data leftRes = zd, rightRes = zd;
    for (; l < r; l /= 2, r /= 2) {
      if (l & 1) leftRes = ud(leftRes, data[l++]);
      if (r & 1) rightRes = ud(data[--r], rightRes);
    }
    return ud(leftRes, rightRes);
  }

  // l \in [0; n) && ok(get(l, l), l);
  // returns last r: ok(get(l, r), r)
  template<typename C>
  int lastTrue(int l, C ok) {
    l += n;
    for (int shift = h; shift > 0; --shift) push(l >> shift);
    Data cur = zd;
    do {
      l >>= __builtin_ctz(l);
      Data with1;
      with1 = ud(cur, data[l]);
      if (ok(with1, right(l))) {
        cur = with1;
        ++l;
      } else {
        while (l < n) {
          push(l);
          Data with2;
          with2 = ud(cur, data[2 * l]);
          if (ok(with2, right(2 * l))) {
            cur = with2;
            l = 2 * l + 1;
          } else {
            l = 2 * l;
          }
        }
        return l - n;
      }
    } while (l & (l - 1));
    return n;
  }

  // r \in [0; n) && ok(get(r, r), r);
  // returns first l: ok(get(l, r), l)
  template<typename C>
  int firstTrue(int r, C ok) {
    r += n;
    for (int shift = h; shift > 0; --shift) push((r - 1) >> shift);
    Data cur = zd;
    while (r & (r - 1)) {
      r >>= __builtin_ctz(r);
      Data with1;
      with1 = ud(data[--r], cur);
      if (ok(with1, left(r))) {
        cur = with1;
      } else {
        while (r < n) {
          push(r);
          Data with2;
          with2 = ud(data[2 * r + 1], cur);
          if (ok(with2, left(2 * r + 1))) {
            cur = with2;
            r = 2 * r;
          } else {
            r = 2 * r + 1;
          }
        }
        return r - n + 1;
      }
    }
    return 0;
  }
};

int32_t main() {
  cin.tie(0);ios_base::sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m, q;
    cin >> n >> m >> q;

    vector <pair <int, int> > e;
    for (int i = 0; i < m; ++i) {
      int u, v; cin >> u >> v;u--; v--;
      e.app({v,u});
    }

    vector <int> c(n);
    for (int i = 0; i < n; ++i) {
      cin >> c[i];
    }



    DominatorTree d(n,e,0);
    auto par = d.idom;

    debugv(par);

    vector <vector <int> > tree(n);
    for (int i = 1; i < n; ++i) {
      tree[par[i]].push_back(i);
    }
    vector <int> in, cnt(n), up(n), l(n);
    function <void(int)> dfs = [&] (int u) {
      in.app(u); cnt[u] = 1;
      for (int v : tree[u]) {
        dfs(v);
        cnt[u] += cnt[v];
      }
    };
    dfs(0);
    auto comp = [&] (int u, int v) {
      return cnt[u] > cnt[v];
    };
    for (int i = 0; i < n; ++i) {
      sort(all(tree[i]), comp);
    }
    for (int u : in) {
      if (u != tree[par[u]].front()) {
        up[u] = u;
      }
      else {
        up[u] = up[par[u]];
      }
    }
    in.clear();
    int ptr = 0;
    function <void(int)> go = [&] (int u) {
        in.app(u);
        l[u]=ptr++;
        for (int v : tree[u]) {
          go(v);
        }
    };
    go(0);

    auto upd = [&] (int u, auto fun) {
      while (true) {
        fun(l[up[u]], l[u] + 1);
        if (up[u] == 0) {
          break;
        }
        u = par[up[u]];
      }
    };

    const int INF = 1e18;
    MassSegmentTree segtree(n, pair{INF, INF}, pair{0LL, INF}, 
      [](auto x, auto y) { return pair{min(x.first, y.first), min(x.second, y.second)}; },
      [](auto x, auto y) { return pair{x.first + y.first, min(x.second + y.first, y.second)}; },
      [](auto x, auto y, int){ return pair{min(x.first + y.first, x.second + y.second), x.second}; }, 
      [&](int i) { return pair{INF, c[in[i]]}; });


    debugv(l);
    debugv(up);
    auto print = [&](){
    #ifdef LOCAL
      for (int i = 0; i < n; ++i) cout << segtree.get(i,i+1).first<<' ';cout << endl;
        #endif
    };

    int mod = 0;
    auto dpmin = [&] () {
      return min(segtree.get(0, n).first, 0LL) + mod;
    };
    for (int i = 0; i < q; ++i) {
      int a, b; cin >> a >> b;
      a--;
      int MIN = dpmin();
      //debug(MIN);
      upd(a, [&](int l, int r) { debug(l,r);segtree.update(l, r, pair{0LL, MIN - mod}); });
      mod += b;
      upd(a, [&](int l, int r) { segtree.update(l, r, pair{-b, INF}); });
      print();

      cout << dpmin() << ' ';
    }
    cout << '\n';
  } 
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

3
7 6 4
2 1
3 1
4 2
5 2
6 3
7 3
4 3 5 2 2 1 1
4 2
5 2
6 2
7 2
5 6 4
1 3
3 2
2 1
4 2
5 4
2 5
10000 10000 2 100 5
5 1000
4 1000
3 1000
4 1000
4 4 1
2 1
3 1
4 2
4 3
100 1 1 100
4 10

output:


result: