oj.uz

Submission #417938

# Submission time Handle Problem Language Result Execution time Memory
417938 2021-06-04T15:42:29 Z parsabahrami Sumtree (INOI20_sumtree) C++17
100 / 100
 1494 ms 129148 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii; 

#define SZ(x) (int) (x).size();
#define F     first
#define S     second
#define int   ll

int Pow(int a, int b, int md, int ret = 1) {
	for (; b; b >>= 1, a = 1ll * a * a % md) 
		if (b & 1) ret = 1ll * ret * a % md;
	return ret;
}

const int N = 5e5 + 10, MOD = 1e9 + 7;
int F[N], St[N], Ft[N], I[N], hv[N], hd[N], S[N], P[N], val[N], H[N], n, q, R, timer;
vector<int> adj[N]; set<pii> st[N]; ll ret; int cnt = 0;
struct node {
	ll d, lz; node *lc, *rc; 

	node() : d(0), lz(0), lc(nullptr), rc(nullptr) {}

	void bld(int l = 0, int r = n) {
		if (r - l < 2) return;
		lc = new node(); rc = new node();
		int md = (l + r) >> 1;
		lc->bld(l, md), rc->bld(md, r);
	}

	void shift() { 
		if (!lz) return;
		d += lz;
		if (lc) lc->lz += lz;
		if (rc) rc->lz += lz;
		lz = 0;
	}

	void upd(int ql, int qr, ll x, int l = 0, int r = n) {
		shift();
		if (qr <= l || r <= ql) return;
		if (ql <= l && r <= qr) { lz += x; return shift(); }
		int md = (l + r) >> 1;
		lc->upd(ql, qr, x, l, md), rc->upd(ql, qr, x, md, r);
		d = min(lc->d, rc->d);
	}

	ll get(int p, int l = 0, int r = n) {
        shift();
		if (r - l < 2) return d;
		int md = (l + r) >> 1;
		return p < md ? lc->get(p, l, md) : rc->get(p, md, r);
	}
};
node *A, *B;

void preDFS(int v, int p = -1) {
	S[v] = 1; P[v] = p;
	for (int u : adj[v]) 
		if (u != p) { H[u] = H[v] + 1, preDFS(u, v), S[v] += S[u];
			if (S[hv[v]] < S[u]) hv[v] = u; }
}

void hldDFS(int v, int p = -1) {
	if (!~p) hd[v] = v;
	St[v] = timer++;
	if (hv[v]) 
		hd[hv[v]] = hd[v], hldDFS(hv[v], v);
	for (int u : adj[v])
		if (u != p && u != hv[v]) 
			hldDFS(hd[u] = u, v);
	Ft[v] = timer;
}

int C(int x, int y) {
	if (x < y || y < 0) return 0;
	return F[x] * 1ll * I[y] % MOD * I[x - y] % MOD;
}

void mul(int x) {
    if (!x) cnt++;
    else ret = x * ret % MOD;
}

void div(int x) {
    if (!x) cnt--;
    else ret = Pow(x, MOD - 2, MOD) * ret % MOD;
}

int32_t main() {
	scanf("%lld%lld", &n, &R);
	F[0] = 1; st[1].insert(pii(0, 1)); val[1] = R;
	for (int i = 1; i < N; i++)  
		F[i] = 1ll * F[i - 1] * i % MOD;
	I[N - 1] = Pow(F[N - 1], MOD - 2, MOD);
	for (int i = N - 1; i; i--) 
		I[i - 1] = 1ll * I[i] * i % MOD;
	for (int i = 1; i < n; i++) {
		int u, v; scanf("%lld%lld", &u, &v); 
		adj[u].push_back(v);
		adj[v].push_back(u);
	} 
	A = new node(), B = new node(); A->bld(), B->bld(); B->upd(0, 1, R);
	preDFS(1); hldDFS(1);
	printf("%lld\n", C(R + n - 1, n - 1)); ret = C(R + n - 1, n - 1);
	for (int i = 1; i <= n; i++) 
		A->upd(St[i], St[i] + 1, S[i]);
	for (scanf("%lld", &q); q; q--) {
		int t, v, x; scanf("%lld%lld", &t, &v);
		if (t < 2) {
			scanf("%lld", &x); ll sub = A->get(St[v]); B->upd(St[v], St[v] + 1, x);
			ll y = B->get(St[v]); val[v] = x;
            mul(C(y + sub - 1, y));
			int u = P[v];
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[u]) {
				A->upd(St[hd[u]], St[u] + 1, -sub); 
				B->upd(St[hd[u]], St[u] + 1, -y);
				u = P[hd[u]]; 
			}
			ll pr = prev(st[hd[u]].lower_bound(pii(St[u], n + 1)))->S;
			st[hd[v]].insert(pii(St[v], v));
			ll cpr = A->get(St[pr]); ll z = B->get(St[pr]);
            div(C(cpr - 1 + z, z));
			A->upd(St[pr], St[u] + 1, -sub); B->upd(St[pr], St[u] + 1, -y); 
			z = B->get(St[pr]); cpr = A->get(St[pr]);
            mul(C(cpr - 1 + z, z));
		} else {
            ll sub = A->get(St[v]), y = B->get(St[v]);
            div(C(y + sub - 1, y));
			int u = P[v]; st[hd[v]].erase({St[v], v});
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[u]) {
				A->upd(St[hd[u]], St[u] + 1, sub); 
				B->upd(St[hd[u]], St[u] + 1, y);
				u = P[hd[u]]; 
			}
			ll pr = prev(st[hd[u]].lower_bound(pii(St[u], n + 1)))->S;
			ll cpr = A->get(St[pr]); ll z = B->get(St[pr]); 
            div(C(cpr - 1 + z, z));
			A->upd(St[pr], St[u] + 1, sub); B->upd(St[pr], St[u] + 1, y); 
			z = B->get(St[pr]); cpr = A->get(St[pr]); 
			mul(C(cpr - 1 + z, z)); B->upd(St[v], St[v] + 1, -val[v]);
		}
        if (cnt) printf("0\n");
        else printf("%lld\n", ret);
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%lld%lld", &n, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   int u, v; scanf("%lld%lld", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:111:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |  for (scanf("%lld", &q); q; q--) {
      |       ~~~~~^~~~~~~~~~~~
Main.cpp:112:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   int t, v, x; scanf("%lld%lld", &t, &v);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:114:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |    scanf("%lld", &x); ll sub = A->get(St[v]); B->upd(St[v], St[v] + 1, x);
      |    ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 107964 KB Output is correct
2 Correct 278 ms 107916 KB Output is correct
3 Correct 300 ms 108080 KB Output is correct
4 Correct 281 ms 107880 KB Output is correct
5 Correct 233 ms 103748 KB Output is correct
6 Correct 31 ms 44352 KB Output is correct
7 Correct 32 ms 44260 KB Output is correct
8 Correct 31 ms 44236 KB Output is correct
9 Correct 341 ms 101836 KB Output is correct
10 Correct 336 ms 101576 KB Output is correct
11 Correct 328 ms 101804 KB Output is correct
12 Correct 300 ms 98896 KB Output is correct
13 Correct 244 ms 102080 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 43340 KB Output is correct
2 Correct 29 ms 43364 KB Output is correct
3 Correct 29 ms 43324 KB Output is correct
4 Correct 30 ms 43332 KB Output is correct
5 Correct 32 ms 43472 KB Output is correct
6 Correct 37 ms 44064 KB Output is correct
7 Correct 35 ms 44068 KB Output is correct
8 Correct 34 ms 44028 KB Output is correct
9 Correct 37 ms 44316 KB Output is correct
10 Correct 38 ms 44360 KB Output is correct
11 Correct 37 ms 44360 KB Output is correct
12 Correct 31 ms 44264 KB Output is correct
13 Correct 37 ms 44340 KB Output is correct
14 Correct 37 ms 44316 KB Output is correct
15 Correct 37 ms 44492 KB Output is correct
16 Correct 38 ms 44444 KB Output is correct
17 Correct 37 ms 44372 KB Output is correct
18 Correct 34 ms 43800 KB Output is correct
19 Correct 38 ms 44372 KB Output is correct
20 Correct 34 ms 43988 KB Output is correct
21 Correct 33 ms 44096 KB Output is correct
22 Correct 30 ms 43468 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 109392 KB Output is correct
2 Correct 389 ms 110460 KB Output is correct
3 Correct 326 ms 109912 KB Output is correct
4 Correct 470 ms 112256 KB Output is correct
5 Correct 657 ms 112452 KB Output is correct
6 Correct 33 ms 44492 KB Output is correct
7 Correct 32 ms 44336 KB Output is correct
8 Correct 34 ms 44404 KB Output is correct
9 Correct 803 ms 110108 KB Output is correct
10 Correct 709 ms 108484 KB Output is correct
11 Correct 805 ms 108040 KB Output is correct
12 Correct 766 ms 109036 KB Output is correct
13 Correct 627 ms 129136 KB Output is correct
14 Correct 635 ms 129148 KB Output is correct
15 Correct 640 ms 129012 KB Output is correct
16 Correct 643 ms 129024 KB Output is correct
17 Correct 641 ms 129120 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1403 ms 107500 KB Output is correct
2 Correct 1434 ms 107128 KB Output is correct
3 Correct 1426 ms 107644 KB Output is correct
4 Correct 1371 ms 107388 KB Output is correct
5 Correct 1316 ms 104224 KB Output is correct
6 Correct 1438 ms 107436 KB Output is correct
7 Correct 1083 ms 77124 KB Output is correct
8 Correct 1030 ms 77264 KB Output is correct
9 Correct 1392 ms 107464 KB Output is correct
10 Correct 1285 ms 107508 KB Output is correct
11 Correct 1272 ms 107628 KB Output is correct
12 Correct 977 ms 77236 KB Output is correct
13 Correct 632 ms 75084 KB Output is correct
14 Correct 772 ms 75644 KB Output is correct
15 Correct 838 ms 75948 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 107964 KB Output is correct
2 Correct 278 ms 107916 KB Output is correct
3 Correct 300 ms 108080 KB Output is correct
4 Correct 281 ms 107880 KB Output is correct
5 Correct 233 ms 103748 KB Output is correct
6 Correct 31 ms 44352 KB Output is correct
7 Correct 32 ms 44260 KB Output is correct
8 Correct 31 ms 44236 KB Output is correct
9 Correct 341 ms 101836 KB Output is correct
10 Correct 336 ms 101576 KB Output is correct
11 Correct 328 ms 101804 KB Output is correct
12 Correct 300 ms 98896 KB Output is correct
13 Correct 244 ms 102080 KB Output is correct
14 Correct 28 ms 43340 KB Output is correct
15 Correct 29 ms 43364 KB Output is correct
16 Correct 29 ms 43324 KB Output is correct
17 Correct 30 ms 43332 KB Output is correct
18 Correct 32 ms 43472 KB Output is correct
19 Correct 37 ms 44064 KB Output is correct
20 Correct 35 ms 44068 KB Output is correct
21 Correct 34 ms 44028 KB Output is correct
22 Correct 37 ms 44316 KB Output is correct
23 Correct 38 ms 44360 KB Output is correct
24 Correct 37 ms 44360 KB Output is correct
25 Correct 31 ms 44264 KB Output is correct
26 Correct 37 ms 44340 KB Output is correct
27 Correct 37 ms 44316 KB Output is correct
28 Correct 37 ms 44492 KB Output is correct
29 Correct 38 ms 44444 KB Output is correct
30 Correct 37 ms 44372 KB Output is correct
31 Correct 34 ms 43800 KB Output is correct
32 Correct 38 ms 44372 KB Output is correct
33 Correct 34 ms 43988 KB Output is correct
34 Correct 33 ms 44096 KB Output is correct
35 Correct 30 ms 43468 KB Output is correct
36 Correct 328 ms 109392 KB Output is correct
37 Correct 389 ms 110460 KB Output is correct
38 Correct 326 ms 109912 KB Output is correct
39 Correct 470 ms 112256 KB Output is correct
40 Correct 657 ms 112452 KB Output is correct
41 Correct 33 ms 44492 KB Output is correct
42 Correct 32 ms 44336 KB Output is correct
43 Correct 34 ms 44404 KB Output is correct
44 Correct 803 ms 110108 KB Output is correct
45 Correct 709 ms 108484 KB Output is correct
46 Correct 805 ms 108040 KB Output is correct
47 Correct 766 ms 109036 KB Output is correct
48 Correct 627 ms 129136 KB Output is correct
49 Correct 635 ms 129148 KB Output is correct
50 Correct 640 ms 129012 KB Output is correct
51 Correct 643 ms 129024 KB Output is correct
52 Correct 641 ms 129120 KB Output is correct
53 Correct 1403 ms 107500 KB Output is correct
54 Correct 1434 ms 107128 KB Output is correct
55 Correct 1426 ms 107644 KB Output is correct
56 Correct 1371 ms 107388 KB Output is correct
57 Correct 1316 ms 104224 KB Output is correct
58 Correct 1438 ms 107436 KB Output is correct
59 Correct 1083 ms 77124 KB Output is correct
60 Correct 1030 ms 77264 KB Output is correct
61 Correct 1392 ms 107464 KB Output is correct
62 Correct 1285 ms 107508 KB Output is correct
63 Correct 1272 ms 107628 KB Output is correct
64 Correct 977 ms 77236 KB Output is correct
65 Correct 632 ms 75084 KB Output is correct
66 Correct 772 ms 75644 KB Output is correct
67 Correct 838 ms 75948 KB Output is correct
68 Correct 29 ms 43328 KB Output is correct
69 Correct 29 ms 43324 KB Output is correct
70 Correct 1010 ms 113672 KB Output is correct
71 Correct 1037 ms 113704 KB Output is correct
72 Correct 1039 ms 113860 KB Output is correct
73 Correct 1057 ms 113708 KB Output is correct
74 Correct 1175 ms 113604 KB Output is correct
75 Correct 1004 ms 110464 KB Output is correct
76 Correct 1389 ms 107640 KB Output is correct
77 Correct 1494 ms 107760 KB Output is correct
78 Correct 1349 ms 108836 KB Output is correct
79 Correct 1135 ms 110532 KB Output is correct
80 Correct 1203 ms 107580 KB Output is correct
81 Correct 1264 ms 109788 KB Output is correct
82 Correct 1116 ms 104748 KB Output is correct
83 Correct 763 ms 111848 KB Output is correct
84 Correct 789 ms 110840 KB Output is correct
85 Correct 768 ms 110648 KB Output is correct