QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#569980#8222. 投票游戏wsyear0 108ms51484kbC++233.9kb2024-09-17 13:03:292024-09-17 13:03:30

Judging History

你现在查看的是最新测评结果

  • [2024-09-17 13:03:30]
  • 评测
  • 测评结果:0
  • 用时:108ms
  • 内存:51484kb
  • [2024-09-17 13:03:29]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 200010;
const int maxm = maxn * 4;
mt19937 rnd(1145141);

struct node {
  ll sumb, mn;
  node() { sumb = mn = 0; }
  node(ll f, ll b) { sumb = b, mn = f; }
  friend node operator+(node x, node y) {
    node res;
    res.sumb = x.sumb + y.sumb;
    res.mn = min(x.mn, x.sumb + y.mn);
    return res;
  }
} sum[maxm], val[maxm];

int sid, n, q, fa[maxn], rt[maxn], ls[maxm], rs[maxm], kval[maxm], tot;
ll a[maxn], b[maxn], f[maxn], bsum[maxn], g[maxn];
pll t[maxm];
vector<int> e[maxn];

int nnd(ll f, ll b, int x) {
  t[++tot] = pll(f, x), sum[tot] = val[tot] = node(f, b);
  return kval[tot] = rnd(), tot;
}

void pushup(int x) {
  sum[x] = val[x];
  if (ls[x]) sum[x] = sum[ls[x]] + sum[x];
  if (rs[x]) sum[x] = sum[x] + sum[rs[x]];
}

int merge(int x, int y) {
  if (!x || !y) return x ^ y;
  if (kval[x] < kval[y]) return rs[x] = merge(rs[x], y), pushup(x), x;
  else return ls[y] = merge(x, ls[y]), pushup(y), y;
}

void split(int x, pll v, int &p, int &q) {
  if (!x) return p = q = 0, void();
  if (t[x] >= v) p = x, split(rs[x], v, rs[p], q);
  else q = x, split(ls[x], v, p, ls[q]);
  pushup(x);
}

ll find(int x, ll lim) {
  if (ls[x] && sum[ls[x]].mn < lim) return find(ls[x], lim);
  if (sum[ls[x]].sumb + val[x].mn < lim) return sum[ls[x]].sumb;
  return sum[ls[x]].sumb + val[x].sumb + find(rs[x], lim - sum[ls[x]].sumb - val[x].sumb);
}

void show(int x) {
  if (!x) return;
  show(ls[x]);
  cerr << "(" << val[x].sumb << "," << val[x].mn << ") ";
  show(rs[x]);
}

void ins(int &rt, ll f, ll b, ll x) {
  int p, q;
  split(rt, pll(f, b), p, q);
  rt = merge(merge(p, nnd(f, b, x)), q);
}

void del(int &rt, ll f, ll b, ll x) {
  int p, w, q;
  split(rt, pll(f, x), p, q), split(p, pll(f, x + 1), p, w);
  rt = merge(p, q);
}

void solve(int u) {
  vector<pll> vec;
  ll sum = 0;
  for (int v : e[u]) {
    solve(v), sum += b[v];
    vec.emplace_back(f[v], v);
  }
  // 按照 f[v] 排序之后第一个 a[u] + sum - sumb[i - 1] > f[i] 的位置
  // 也就是 a[u] + sum > f[i] + sumb[i - 1]
  sort(ALL(vec), greater<>());
  rep (i, 0, SZ(vec) - 1) {
    if (a[u] + sum > vec[i].fi) return f[u] = a[u] + sum, void();
    sum -= b[vec[i].se];
  }
  f[u] = a[u];
}

void calc(int u) {
  if (sum[rt[u]].mn >= a[u] + bsum[u]) return f[u] = a[u], void();
  ll res = find(rt[u], a[u] + bsum[u]);
  f[u] = a[u] + bsum[u] - res;
}

void dfs(int u) {
  for (int v : e[u]) {
    dfs(v), ins(rt[u], f[v], b[v], v);
  }
  calc(u);
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> sid >> n >> q;
  rep (i, 2, n) cin >> fa[i];
  rep (i, 2, n) e[fa[i]].emplace_back(i);
  rep (i, 1, n) cin >> a[i];
  rep (i, 1, n) cin >> b[i], bsum[fa[i]] += b[i];
  solve(1);
  rep (i, 1, n) g[i] = f[i];
  dfs(1);
  // rep (i, 1, n) cerr << f[i] << " \n"[i == n];
  // rep (i, 1, n) assert(f[i] == g[i]);
  while (q--) {
    int op, x, y;
    cin >> op >> x;
    if (op == 1) {
      int p = x;
      while (fa[p]) {
        del(rt[fa[p]], f[p], b[p], p);
        p = fa[p];
      }
      bsum[fa[x]] -= b[x];
      cin >> a[x] >> b[x];
      bsum[fa[x]] += b[x];
      while (x) {
        calc(x);
        if (fa[x]) ins(rt[fa[x]], f[x], b[x], x);
        x = fa[x];
      }
    } else {
      cin >> y;
      solve(1);
      cout << (pll(f[x], x) > pll(f[y], y) ? 0 : 1) << '\n';
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

20 500
1 1 3 1 3 5 6 6 7 3 5 3 9 5 4 7 7 18 2
42129194 82765784 1447057 29726963 82321558 32094641 22474113 49277574 27527633 20746795 47630926 92888389 26787144 80703040 43876864 97991729 12117966 75633318 33577855 93462601
69163546 49621952 45236756 46447931 34085269 55246550 54414402 99593046 103...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #13:

score: 0
Wrong Answer
time: 39ms
memory: 43956kb

input:

200 200000
1 2 3 3 5 3 1 6 2 9 11 5 5 2 4 9 17 8 1 4 10 20 18 20 23 13 16 28 15 4 6 27 26 11 30 25 10 2 13 23 25 35 4 8 40 43 36 26 7 27 45 35 14 31 54 45 9 8 9 54 16 32 62 9 29 2 43 39 34 39 27 2 52 56 6 9 48 26 66 28 35 57 79 13 71 61 38 43 80 26 61 26 79 1 24 64 79 15 41 42 56 55 6 24 92 43 89 76...

output:

0

result:

wrong answer Answer contains longer sequence [length = 100045], but output contains 1 elements

Subtask #4:

score: 0
Wrong Answer

Test #18:

score: 0
Wrong Answer
time: 108ms
memory: 51484kb

input:

200 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

0

result:

wrong answer 1st numbers differ - expected: '1', found: '0'

Subtask #5:

score: 0
Wrong Answer

Test #26:

score: 0
Wrong Answer
time: 38ms
memory: 43040kb

input:

200 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

1

result:

wrong answer Answer contains longer sequence [length = 100455], but output contains 1 elements

Subtask #6:

score: 0
Skipped

Dependency #1:

0%