oj.uz

Submission #417259

# Submission time Handle Problem Language Result Execution time Memory
417259 2021-06-03T14:03:01 Z parsabahrami Sumtree (INOI20_sumtree) C++17
10 / 100
 774 ms 157384 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

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]; int seg[N << 2], lz[N << 2]; set<pii> st[N]; int ret;
struct node {
	int 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, int 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);
	}

	int get(int p, int l = 0, int r = n) {
		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;
}

int main() {
	scanf("%d%d", &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("%d%d", &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("%d\n", 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("%d", &q); q; q--) {
		int t, v, x; scanf("%d%d", &t, &v);
		if (t < 2) {
			scanf("%d", &x); int sub = A->get(St[v]); B->upd(St[v], St[v] + 1, x);
			int y = B->get(St[v]); val[v] = x;
			ret = 1ll * ret * C(y + sub - 1, sub - 1) % MOD;
			int u = P[v];
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[v]) {
				A->upd(St[hd[u]], St[u] + 1, -sub); 
				B->upd(St[hd[u]], St[u] + 1, -y);
				u = P[hd[u]]; 
			}
			int pr = prev(st[hd[u]].lower_bound(pii(St[v], -1)))->S;
			st[hd[v]].insert(pii(St[v], v));
			int cpr = A->get(St[pr]); int z = B->get(St[pr]); 
			ret = 1ll * ret * Pow(C(cpr - 1 + z, z), MOD - 2, MOD) % MOD;
			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]); 
			ret = 1ll * ret * C(cpr - 1 + z, z) % MOD;
		} else {
            int sub = A->get(St[v]), y = B->get(St[v]);
			ret = 1ll * ret * Pow(C(y + sub - 1, sub - 1), MOD - 2, MOD) % MOD;
			int u = P[v]; st[hd[v]].erase({St[v], v});
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[v]) {
				A->upd(St[hd[u]], St[u] + 1, sub); 
				B->upd(St[hd[u]], St[u] + 1, y);
				u = P[hd[u]]; 
			}
			int pr = prev(st[hd[u]].lower_bound(pii(St[v], -1)))->S;
			int cpr = A->get(St[pr]); int z = B->get(St[pr]); 
			ret = 1ll * ret * Pow(C(cpr - 1 + z, z), MOD - 2, MOD) % MOD;
			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]); 
			ret = 1ll * ret * C(cpr - 1 + z, z) % MOD; B->upd(St[v], St[v] + 1, -val[v]);
		}
		printf("%d\n", ret);
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  scanf("%d%d", &n, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:99:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  for (scanf("%d", &q); q; q--) {
      |       ~~~~~^~~~~~~~~~
Main.cpp:100:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |   int t, v, x; scanf("%d%d", &t, &v);
      |                ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:102:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |    scanf("%d", &x); int 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 320 ms 86608 KB Output is correct
2 Correct 296 ms 87092 KB Output is correct
3 Correct 319 ms 87128 KB Output is correct
4 Correct 303 ms 87076 KB Output is correct
5 Correct 264 ms 82416 KB Output is correct
6 Correct 36 ms 40272 KB Output is correct
7 Correct 35 ms 40004 KB Output is correct
8 Correct 38 ms 40104 KB Output is correct
9 Correct 402 ms 77664 KB Output is correct
10 Correct 414 ms 77452 KB Output is correct
11 Correct 386 ms 77588 KB Output is correct
12 Correct 382 ms 75636 KB Output is correct
13 Correct 274 ms 82824 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 39500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 388 ms 86744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 774 ms 157384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 86608 KB Output is correct
2 Correct 296 ms 87092 KB Output is correct
3 Correct 319 ms 87128 KB Output is correct
4 Correct 303 ms 87076 KB Output is correct
5 Correct 264 ms 82416 KB Output is correct
6 Correct 36 ms 40272 KB Output is correct
7 Correct 35 ms 40004 KB Output is correct
8 Correct 38 ms 40104 KB Output is correct
9 Correct 402 ms 77664 KB Output is correct
10 Correct 414 ms 77452 KB Output is correct
11 Correct 386 ms 77588 KB Output is correct
12 Correct 382 ms 75636 KB Output is correct
13 Correct 274 ms 82824 KB Output is correct
14 Incorrect 30 ms 39500 KB Output isn't correct
15 Halted 0 ms 0 KB -