QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#163870 | #6737. Neighbourhood | ucup-team1209# | WA | 3415ms | 282288kb | C++20 | 4.3kb | 2023-09-04 16:00:33 | 2023-09-04 16:00:34 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
using std::cin;
using std::cout;
using u64 = unsigned long long;
using ll = long long;
struct ds {
int B, n;
std::vector<ll> a;
struct block {
std::vector<ll> elem;
ll add;
void init() { sort(elem.begin(), elem.end()); }
ll leq(ll x) {
return upper_bound(elem.begin(), elem.end(), x - add) - elem.begin();
}
};
std::vector<block> v;
void init(std::vector<ll> s) {
a = s, n = a.size();
for(B = 0;3 << (2 * B) < a.size();) ++ B;
v.resize(((n - 1) >> B) + 1);
for(int i = 0;i < n;++i) v[i >> B].elem.push_back(a[i]);
for(block & x : v) x.init();
}
void badd(int l, int r, int val) {
for(int i = l;i <= r;++i) {
a[i] += val;
}
copy(a.begin() + (l >> B << B), a.begin() + std::min((l >> B << B) + (1 << B), n), v[l >> B].elem.begin());
v[l >> B].init();
}
void rangeadd(int l, int r, int val) {
if((l >> B) == (r >> B)) {
badd(l, r, val);
return ;
}
badd(l, l | ((1 << B) - 1), val);
badd(r >> B << B, r, val);
for(int i = (l >> B) + 1;i < (r >> B);++i) {
v[i].add += val;
}
}
int qry(int l, int r, ll val) {
if(val < 0) return 0;
ll ans = 0;
for(int i = 0;i < (l >> B);++i) {
ans += v[i].leq(val);
}
for(int i = (r >> B) + 1;i < (int) v.size();++i) {
ans += v[i].leq(val);
}
const ll vL = val - v[l >> B].add;
const ll vR = val - v[r >> B].add;
for(int i = (l >> B) << B;i < l;++i) {
ans += a[i] <= vL;
}
for(int i = r + 1, end = std::min((r >> B << B) + (1 << B), n);i < end;++i) {
ans += a[i] <= vR;
}
return ans;
}
int qp(int p) {
return a[p] + v[p >> B].add;
}
};
const int N = 200005;
int n, q;
struct edge { int to, nxt, v, id; } e[N << 1];
int h[N], num;
void link(int x, int y, int v, int id) {
e[++num] = {y, h[x], v, id}, h[x] = num;
e[++num] = {x, h[y], v, id}, h[y] = num;
}
ds d[N];
int vis[N], size[N];
void dfs0(int x, int fa = 0) {
size[x] = 1;
for(int i = h[x];i;i = e[i].nxt) if(e[i].to != fa && !vis[e[i].to]) {
dfs0(e[i].to, x);
size[x] += size[e[i].to];
}
}
int mn, root;
void dfs1(int x, int s, int fa = 0) {
int max = s - size[x];
for(int i = h[x];i;i = e[i].nxt) if(e[i].to != fa && !vis[e[i].to]) {
dfs1(e[i].to, s, x);
max = std::max(max, size[e[i].to]);
}
if(max < mn) {
mn = max;
root = x;
}
}
int getroot(int x) {
dfs0(x), mn = 1e9, dfs1(x, size[x]);
return root;
}
int in[20][N], out[20][N], bel[20][N], cnt;
ll dep[20][N];
int dep_x[N], anc_x[N];
std::vector<ll> dis;
std::vector<std::pair<ds*, std::pair<int, int>>> mdfs[N];
int now_root;
void dfs2(int x, int * in, int * out, int * bel, ll * dep, int fa = 0) {
in[x] = ++ cnt;
bel[x] = bel[fa];
dis.push_back(dep[x]);
for(int i = h[x];i;i = e[i].nxt) if(e[i].to != fa && !vis[e[i].to]) {
dep[e[i].to] = dep[x] + e[i].v;
dfs2(e[i].to, in, out, bel, dep, x);
mdfs[e[i].id].emplace_back(d + now_root, std::make_pair(in[e[i].to], out[e[i].to]));
}
out[x] = cnt;
}
int solve(int x, int d) {
x = getroot(x), vis[x] = 1;
dep_x[x] = d;
now_root = x;
cnt = 0;
in[d][x] = cnt;
dis = {0};
for(int i = h[x];i;i = e[i].nxt) if(!vis[e[i].to]) {
dep[d][e[i].to] = e[i].v;
bel[d][x] = e[i].to;
dfs2(e[i].to, in[d], out[d], bel[d], dep[d], x);
bel[d][x] = 0;
mdfs[e[i].id].emplace_back(::d + now_root, std::make_pair(in[d][e[i].to], out[d][e[i].to]));
}
out[d][x] = cnt;
::d[x].init(dis);
for(int i = h[x];i;i = e[i].nxt) if(!vis[e[i].to]) {
anc_x[solve(e[i].to, d + 1)] = x;
}
return x;
}
int qry(int x, ll D) {
ll ans = 1 + d[x].qry(0, 0, D);
for(int t = x;x = anc_x[x];) {
int dp = dep_x[x], s = bel[dp][t];
ans += d[x].qry(in[dp][s], out[dp][s], D - d[x].qp(in[dp][t]));
}
return ans;
}
int w[N];
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
#ifdef zqj
freopen("$.in", "r", stdin);
#endif
cin >> n >> q;
for(int i = 1, x, y, w;i < n;++i) {
cin >> x >> y >> w;
::w[i] = w;
link(x, y, w, i);
}
solve(1, 0);
for(int i = 1;i <= q;++i) {
int type, c, x;
cin >> type;
if(type == 2) {
ll d;
cin >> x >> d;
cout << qry(x, d) << '\n';
} else {
cin >> x >> c;
c -= w[x];
w[x] += c;
for(auto [d, sq] : mdfs[x]) {
d -> rangeadd(sq.first, sq.second, c);
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 34224kb
input:
3 7 1 2 3 2 3 1 2 2 1 2 1 3 2 3 4 1 1 1 2 2 1 2 1 0 2 3 1
output:
2 2 3 3 1 2
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 3415ms
memory: 282288kb
input:
200000 200000 1 2 146181238 2 3 45037818 3 4 176924060 4 5 969365276 5 6 683948619 6 7 356268194 7 8 871634797 8 9 630254480 9 10 283061123 10 11 204904965 11 12 838381393 12 13 516373812 13 14 253862710 14 15 223572474 15 16 114452997 16 17 145251056 17 18 905638436 18 19 375445402 19 20 549829545 ...
output:
1283 112705 6276 19644 114896 3610 35719 172974 18013 20190 12047 9591 48546 26177 53539 11323 156406 174237 196698 41244 48513 56572 26434 1506 13163 12776 23689 80209 17659 180362 41298 653 4387 703 114039 4412 32055 8023 69101 4899 17747 33134 66479 1396 80730 9533 41367 9235 82027 131368 168255 ...
result:
wrong answer 1st numbers differ - expected: '219', found: '1283'