oj.uz

Submission #417297

# Submission time Handle Problem Language Result Execution time Memory
417297 2021-06-03T14:32:33 Z parsabahrami Sumtree (INOI20_sumtree) C++17
10 / 100
 558 ms 157728 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[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[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[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[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 302 ms 87108 KB Output is correct
2 Correct 312 ms 86988 KB Output is correct
3 Correct 344 ms 87096 KB Output is correct
4 Correct 317 ms 86996 KB Output is correct
5 Correct 257 ms 82152 KB Output is correct
6 Correct 32 ms 40396 KB Output is correct
7 Correct 31 ms 40088 KB Output is correct
8 Correct 32 ms 40080 KB Output is correct
9 Correct 404 ms 77764 KB Output is correct
10 Correct 368 ms 77604 KB Output is correct
11 Correct 412 ms 77776 KB Output is correct
12 Correct 379 ms 75920 KB Output is correct
13 Correct 302 ms 83260 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 415 ms 87076 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 558 ms 157728 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 302 ms 87108 KB Output is correct
2 Correct 312 ms 86988 KB Output is correct
3 Correct 344 ms 87096 KB Output is correct
4 Correct 317 ms 86996 KB Output is correct
5 Correct 257 ms 82152 KB Output is correct
6 Correct 32 ms 40396 KB Output is correct
7 Correct 31 ms 40088 KB Output is correct
8 Correct 32 ms 40080 KB Output is correct
9 Correct 404 ms 77764 KB Output is correct
10 Correct 368 ms 77604 KB Output is correct
11 Correct 412 ms 77776 KB Output is correct
12 Correct 379 ms 75920 KB Output is correct
13 Correct 302 ms 83260 KB Output is correct
14 Incorrect 33 ms 39412 KB Output isn't correct
15 Halted 0 ms 0 KB -