oj.uz

Submission #417304

# Submission time Handle Problem Language Result Execution time Memory
417304 2021-06-03T14:35:00 Z parsabahrami Sumtree (INOI20_sumtree) C++17
10 / 100
 937 ms 157916 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) {
        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;
}

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[u]) {
				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[u], -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);
			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]]; 
			}
			int pr = prev(st[hd[u]].lower_bound(pii(St[u], -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:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d", &n, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:100:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  for (scanf("%d", &q); q; q--) {
      |       ~~~~~^~~~~~~~~~
Main.cpp:101:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   int t, v, x; scanf("%d%d", &t, &v);
      |                ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |    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 257 ms 86468 KB Output is correct
2 Correct 255 ms 86436 KB Output is correct
3 Correct 261 ms 86448 KB Output is correct
4 Correct 264 ms 86428 KB Output is correct
5 Correct 241 ms 81676 KB Output is correct
6 Correct 31 ms 40276 KB Output is correct
7 Correct 31 ms 40004 KB Output is correct
8 Correct 31 ms 40004 KB Output is correct
9 Correct 296 ms 77296 KB Output is correct
10 Correct 304 ms 77088 KB Output is correct
11 Correct 314 ms 77180 KB Output is correct
12 Correct 287 ms 75304 KB Output is correct
13 Correct 235 ms 82696 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 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 294 ms 86488 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 937 ms 157916 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 257 ms 86468 KB Output is correct
2 Correct 255 ms 86436 KB Output is correct
3 Correct 261 ms 86448 KB Output is correct
4 Correct 264 ms 86428 KB Output is correct
5 Correct 241 ms 81676 KB Output is correct
6 Correct 31 ms 40276 KB Output is correct
7 Correct 31 ms 40004 KB Output is correct
8 Correct 31 ms 40004 KB Output is correct
9 Correct 296 ms 77296 KB Output is correct
10 Correct 304 ms 77088 KB Output is correct
11 Correct 314 ms 77180 KB Output is correct
12 Correct 287 ms 75304 KB Output is correct
13 Correct 235 ms 82696 KB Output is correct
14 Incorrect 29 ms 39500 KB Output isn't correct
15 Halted 0 ms 0 KB -