QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163870#6737. Neighbourhooducup-team1209#WA 3415ms282288kbC++204.3kb2023-09-04 16:00:332023-09-04 16:00:34

Judging History

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

  • [2023-09-04 16:00:34]
  • 评测
  • 测评结果:WA
  • 用时:3415ms
  • 内存:282288kb
  • [2023-09-04 16:00:33]
  • 提交

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'