oj.uz

Submission #417202

# Submission time Handle Problem Language Result Execution time Memory
417202 2021-06-03T12:57:39 Z parsabahrami Sumtree (INOI20_sumtree) C++17
10 / 100
 553 ms 116596 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 lc id << 1
#define rc lc | 1

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;

void shift(int id, int l, int r) {
	seg[id] += lz[id];
	if (r - l > 1) 
		lz[lc] += lz[id], lz[rc] += lz[id];
	lz[id] = 0;
}

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

int get(int p, int id = 1, int l = 0, int r = n) {
	shift(id, l, r);
	if (r - l < 2) { return seg[id]; }
	int md = (l + r) >> 1;
	return p < md ? get(p, lc, l, md) : get(p, rc, md, r);
}

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);
	}
	preDFS(1); hldDFS(1);
	printf("%d\n", ret = C(r + n - 1, n - 1));
	for (int i = 1; i <= n; i++) 
		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 = get(St[v]);
			ret = 1ll * ret * C((val[v] = x) + sub - 1, sub - 1) % MOD;
			int u = P[v];
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[v]) {
				upd(St[hd[u]], St[u] + 1, -sub); 
				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 = get(St[pr]); ret = 1ll * ret * Pow(C(cpr - 1 + val[pr], val[pr]), MOD - 2, MOD) % MOD;
			upd(St[pr], St[u] + 1, -sub); cpr = get(St[pr]); 
			ret = 1ll * ret * C(cpr - 1 + val[pr], val[pr]) % MOD;
		} else {
			int sub = get(St[v]);
			ret = 1ll * ret * Pow(C(sub + val[v] - 1, val[v]), MOD - 2, MOD) % MOD;
			int u = P[v]; st[hd[v]].erase(pii(St[v], v));
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[v]) {
				upd(St[hd[u]], St[u] + 1, sub); 
				u = P[hd[u]];
			}
			int pr = prev(st[hd[u]].lower_bound(pii(St[v], -1)))->S;
			int cpr = get(St[pr]); ret = 1ll * ret * Pow(C(cpr - 1 + val[pr], val[pr]), MOD - 2, MOD) % MOD;
			upd(St[pr], St[u] + 1, sub); cpr = get(St[pr]); 
			ret = 1ll * ret * C(cpr - 1 + val[pr], val[pr]) % MOD;
		}
		printf("%d\n", ret);
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d", &n, &r);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:86:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  for (scanf("%d", &q); q; q--) {
      |       ~~~~~^~~~~~~~~~
Main.cpp:87:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   int t, v, x; scanf("%d%d", &t, &v);
      |                ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:89:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |    scanf("%d", &x); int sub = get(St[v]);
      |    ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 66244 KB Output is correct
2 Correct 257 ms 67172 KB Output is correct
3 Correct 287 ms 67272 KB Output is correct
4 Correct 304 ms 67124 KB Output is correct
5 Correct 254 ms 62544 KB Output is correct
6 Correct 30 ms 40072 KB Output is correct
7 Correct 30 ms 39756 KB Output is correct
8 Correct 30 ms 39824 KB Output is correct
9 Correct 321 ms 58056 KB Output is correct
10 Correct 297 ms 57924 KB Output is correct
11 Correct 346 ms 57924 KB Output is correct
12 Correct 275 ms 57304 KB Output is correct
13 Correct 256 ms 65748 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 66508 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 553 ms 116596 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 273 ms 66244 KB Output is correct
2 Correct 257 ms 67172 KB Output is correct
3 Correct 287 ms 67272 KB Output is correct
4 Correct 304 ms 67124 KB Output is correct
5 Correct 254 ms 62544 KB Output is correct
6 Correct 30 ms 40072 KB Output is correct
7 Correct 30 ms 39756 KB Output is correct
8 Correct 30 ms 39824 KB Output is correct
9 Correct 321 ms 58056 KB Output is correct
10 Correct 297 ms 57924 KB Output is correct
11 Correct 346 ms 57924 KB Output is correct
12 Correct 275 ms 57304 KB Output is correct
13 Correct 256 ms 65748 KB Output is correct
14 Incorrect 27 ms 39484 KB Output isn't correct
15 Halted 0 ms 0 KB -