QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#806208 | #9862. Antivirus | Block of Cats (Maksim Turevskii, Leonid Danilevich, Fedor Ushakov) | RE | 0ms | 0kb | C++23 | 10.5kb | 2024-12-08 23:39:24 | 2024-12-08 23:39:25 |
Judging History
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