oj.uz

Submission #635415

# Submission time Handle Problem Language Result Execution time Memory
635415 2022-08-26T08:38:11 Z S2speed Sumtree (INOI20_sumtree) C++17
100 / 100
 576 ms 64972 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define sze(x) (int)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;

const ll maxn = 2e5 + 17 , maxc = 6e5 + 17 , md = 1e9 + 7 , inf = 2e8;

struct fentree {

	int sz;
	vector<int> val;

	void init(int n){
		sz = n;
		val.assign(sz , 0);
		return;
	}

	void add(int i , int k){
		if(i == -1) return;
		int h = i;
		while(h < sz){
			val[h] += k;
			h |= (h + 1);
		}
		return;
	}

	int cal(int i){
		int h = i , res = 0;
		while(h > -1){
			res += val[h];
			h &= (h + 1); h--;
		}
		return res;
	}

	int cal(int l , int r){
		return cal(r - 1) - cal(l - 1);
	}

};

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll fact[maxc] , _fact[maxc];

void fact_build(){
	fact[0] = 1;
	for(ll i = 1 ; i < maxc ; i++){
		fact[i] = fact[i - 1] * i % md;
	}
	_fact[maxc - 1] = tav(fact[maxc - 1] , md - 2);
	for(ll i = maxc - 2 ; ~i ; i--){
		_fact[i] = _fact[i + 1] * (i + 1) % md;
	}
	return;
}

ll chs(ll n , ll k){
	if(n < k) return 0;
	return fact[n] * _fact[k] % md * _fact[n - k] % md;
}

ll _chs(ll n , ll k){
	if(n < k) return 0;
	return _fact[n] * fact[k] % md * fact[n - k] % md;
}

fentree zt , at , ft;
ll res = 1;
int cnt;
int a[maxn] , z[maxn];
vector<int> adj[maxn];
int jad[maxn][20] , bt[maxn] , et[maxn] , tme = 0;

void pDFS(int r , int par){
	bt[r] = tme++;
	z[r] = 1;
	jad[r][0] = par;
	for(int j = 1 ; j < 20 ; j++){
		if(jad[r][j - 1] == -1) break;
		jad[r][j] = jad[jad[r][j - 1]][j - 1];
	}
	for(auto i : adj[r]){
		if(i == par) continue;
		pDFS(i , r);
		z[r] += z[i];
	}
	et[r] = tme;
	return;
}

void rem(ll n , ll k){
	ll h = _chs(n , k);
	if(h == 0){
		cnt--;
	} else {
		res *= h; res %= md;
	}
	return;
}

void add(ll n , ll k){
	ll h = chs(n , k);
	if(h == 0){
		cnt++;
	} else {
		res *= h; res %= md;
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(jad , -1 , sizeof(jad));
	fact_build();
	ll n;
	cin>>n>>a[0];
	for(ll i = 1 ; i < n ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		adj[v].push_back(u); adj[u].push_back(v);
	}
	pDFS(0 , -1);
	int q;
	cin>>q;
	res = chs(n + a[0] - 1 , n - 1);
	cout<<res<<'\n';
	ft.init(n); zt.init(n); at.init(n);
	for(int e = 0 ; e < q ; e++){
		int t;
		cin>>t;
		if(t == 2){
			int i;
			cin>>i; i--;
			int v = i , pr = ft.cal(bt[i]) - 1;
			for(int j = 19 ; ~j ; j--){
				if(jad[v][j] == -1) continue;
				int u = jad[v][j] , h = ft.cal(bt[u]);
				if(h == pr){
					v = u;
				}
			}
			int zv = z[v] - zt.cal(bt[v] , et[v]) , av = a[v] - at.cal(bt[v] , et[v]);
			rem(zv + av - 1 , zv - 1);
			int zi = z[i] - zt.cal(bt[i] , et[i]) , ai = a[i] - at.cal(bt[i] , et[i]);
			rem(zi + ai - 1 , zi - 1);
			int ji = jad[i][0] , jv = jad[v][0];
			zt.add(bt[ji] , -zi);
			at.add(bt[ji] , -ai);
			if(jv != -1){
				zt.add(bt[jv] , zi);
				at.add(bt[jv] , ai);
			}
			zv = z[v] - zt.cal(bt[v] , et[v]); av = a[v] - at.cal(bt[v] , et[v]);
			add(zv + av - 1 , zv - 1);
			ft.add(bt[i] , -1); ft.add(et[i] , 1);
		} else {
			int i , x;
			cin>>i>>x; i--; a[i] = x;
			int v = i , pr = ft.cal(bt[i]);
			for(int j = 19 ; ~j ; j--){
				if(jad[v][j] == -1) continue;
				int u = jad[v][j] , h = ft.cal(bt[u]);
				if(h == pr){
					v = u;
				}
			}
//			cout<<v<<'\n';
			int zv = z[v] - zt.cal(bt[v] , et[v]) , av = a[v] - at.cal(bt[v] , et[v]);
//			cout<<zv<<' '<<av<<'\n';
//			cout<<res<<' ';
			rem(zv + av - 1 , zv - 1);
//			cout<<res<<' ';
			int zi = z[i] - zt.cal(bt[i] , et[i]) , ai = a[i] - at.cal(bt[i] , et[i]);
			add(zi + ai - 1 , zi - 1);
//			cout<<res<<' ';
			int ji = jad[i][0] , jv = jad[v][0];
			zt.add(bt[ji] , zi);
			at.add(bt[ji] , ai);
			if(jv != -1){
				zt.add(bt[jv] , -zi);
				at.add(bt[jv] , -ai);
			}
			zv = z[v] - zt.cal(bt[v] , et[v]); av = a[v] - at.cal(bt[v] , et[v]);
			add(zv + av - 1 , zv - 1);
//			cout<<res<<'\n';
			ft.add(bt[i] , 1); ft.add(et[i] , -1);
		}
		cout<<(cnt > 0 ? 0 : res)<<'\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 51276 KB Output is correct
2 Correct 217 ms 51252 KB Output is correct
3 Correct 204 ms 51300 KB Output is correct
4 Correct 200 ms 51352 KB Output is correct
5 Correct 150 ms 47284 KB Output is correct
6 Correct 20 ms 30404 KB Output is correct
7 Correct 23 ms 30164 KB Output is correct
8 Correct 25 ms 30164 KB Output is correct
9 Correct 150 ms 43552 KB Output is correct
10 Correct 141 ms 43584 KB Output is correct
11 Correct 147 ms 43576 KB Output is correct
12 Correct 132 ms 42828 KB Output is correct
13 Correct 167 ms 49856 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30036 KB Output is correct
2 Correct 20 ms 30028 KB Output is correct
3 Correct 19 ms 30036 KB Output is correct
4 Correct 20 ms 30056 KB Output is correct
5 Correct 21 ms 30088 KB Output is correct
6 Correct 25 ms 30164 KB Output is correct
7 Correct 25 ms 30228 KB Output is correct
8 Correct 21 ms 30220 KB Output is correct
9 Correct 23 ms 30244 KB Output is correct
10 Correct 26 ms 30344 KB Output is correct
11 Correct 23 ms 30352 KB Output is correct
12 Correct 20 ms 30292 KB Output is correct
13 Correct 25 ms 30324 KB Output is correct
14 Correct 23 ms 30292 KB Output is correct
15 Correct 25 ms 30484 KB Output is correct
16 Correct 22 ms 30328 KB Output is correct
17 Correct 22 ms 30284 KB Output is correct
18 Correct 24 ms 30288 KB Output is correct
19 Correct 23 ms 30304 KB Output is correct
20 Correct 23 ms 30236 KB Output is correct
21 Correct 22 ms 30220 KB Output is correct
22 Correct 18 ms 30036 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 51464 KB Output is correct
2 Correct 222 ms 51944 KB Output is correct
3 Correct 173 ms 52252 KB Output is correct
4 Correct 234 ms 52952 KB Output is correct
5 Correct 322 ms 50584 KB Output is correct
6 Correct 21 ms 30504 KB Output is correct
7 Correct 19 ms 30308 KB Output is correct
8 Correct 21 ms 30348 KB Output is correct
9 Correct 311 ms 46512 KB Output is correct
10 Correct 262 ms 45976 KB Output is correct
11 Correct 218 ms 45844 KB Output is correct
12 Correct 243 ms 45952 KB Output is correct
13 Correct 240 ms 64844 KB Output is correct
14 Correct 242 ms 64840 KB Output is correct
15 Correct 232 ms 64824 KB Output is correct
16 Correct 252 ms 64972 KB Output is correct
17 Correct 234 ms 64964 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 48420 KB Output is correct
2 Correct 320 ms 48392 KB Output is correct
3 Correct 337 ms 48424 KB Output is correct
4 Correct 342 ms 48428 KB Output is correct
5 Correct 350 ms 47612 KB Output is correct
6 Correct 318 ms 48332 KB Output is correct
7 Correct 222 ms 40860 KB Output is correct
8 Correct 297 ms 41052 KB Output is correct
9 Correct 355 ms 48460 KB Output is correct
10 Correct 315 ms 48512 KB Output is correct
11 Correct 394 ms 48712 KB Output is correct
12 Correct 211 ms 41140 KB Output is correct
13 Correct 169 ms 39400 KB Output is correct
14 Correct 250 ms 39664 KB Output is correct
15 Correct 210 ms 39628 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 51276 KB Output is correct
2 Correct 217 ms 51252 KB Output is correct
3 Correct 204 ms 51300 KB Output is correct
4 Correct 200 ms 51352 KB Output is correct
5 Correct 150 ms 47284 KB Output is correct
6 Correct 20 ms 30404 KB Output is correct
7 Correct 23 ms 30164 KB Output is correct
8 Correct 25 ms 30164 KB Output is correct
9 Correct 150 ms 43552 KB Output is correct
10 Correct 141 ms 43584 KB Output is correct
11 Correct 147 ms 43576 KB Output is correct
12 Correct 132 ms 42828 KB Output is correct
13 Correct 167 ms 49856 KB Output is correct
14 Correct 19 ms 30036 KB Output is correct
15 Correct 20 ms 30028 KB Output is correct
16 Correct 19 ms 30036 KB Output is correct
17 Correct 20 ms 30056 KB Output is correct
18 Correct 21 ms 30088 KB Output is correct
19 Correct 25 ms 30164 KB Output is correct
20 Correct 25 ms 30228 KB Output is correct
21 Correct 21 ms 30220 KB Output is correct
22 Correct 23 ms 30244 KB Output is correct
23 Correct 26 ms 30344 KB Output is correct
24 Correct 23 ms 30352 KB Output is correct
25 Correct 20 ms 30292 KB Output is correct
26 Correct 25 ms 30324 KB Output is correct
27 Correct 23 ms 30292 KB Output is correct
28 Correct 25 ms 30484 KB Output is correct
29 Correct 22 ms 30328 KB Output is correct
30 Correct 22 ms 30284 KB Output is correct
31 Correct 24 ms 30288 KB Output is correct
32 Correct 23 ms 30304 KB Output is correct
33 Correct 23 ms 30236 KB Output is correct
34 Correct 22 ms 30220 KB Output is correct
35 Correct 18 ms 30036 KB Output is correct
36 Correct 209 ms 51464 KB Output is correct
37 Correct 222 ms 51944 KB Output is correct
38 Correct 173 ms 52252 KB Output is correct
39 Correct 234 ms 52952 KB Output is correct
40 Correct 322 ms 50584 KB Output is correct
41 Correct 21 ms 30504 KB Output is correct
42 Correct 19 ms 30308 KB Output is correct
43 Correct 21 ms 30348 KB Output is correct
44 Correct 311 ms 46512 KB Output is correct
45 Correct 262 ms 45976 KB Output is correct
46 Correct 218 ms 45844 KB Output is correct
47 Correct 243 ms 45952 KB Output is correct
48 Correct 240 ms 64844 KB Output is correct
49 Correct 242 ms 64840 KB Output is correct
50 Correct 232 ms 64824 KB Output is correct
51 Correct 252 ms 64972 KB Output is correct
52 Correct 234 ms 64964 KB Output is correct
53 Correct 395 ms 48420 KB Output is correct
54 Correct 320 ms 48392 KB Output is correct
55 Correct 337 ms 48424 KB Output is correct
56 Correct 342 ms 48428 KB Output is correct
57 Correct 350 ms 47612 KB Output is correct
58 Correct 318 ms 48332 KB Output is correct
59 Correct 222 ms 40860 KB Output is correct
60 Correct 297 ms 41052 KB Output is correct
61 Correct 355 ms 48460 KB Output is correct
62 Correct 315 ms 48512 KB Output is correct
63 Correct 394 ms 48712 KB Output is correct
64 Correct 211 ms 41140 KB Output is correct
65 Correct 169 ms 39400 KB Output is correct
66 Correct 250 ms 39664 KB Output is correct
67 Correct 210 ms 39628 KB Output is correct
68 Correct 18 ms 30036 KB Output is correct
69 Correct 18 ms 30040 KB Output is correct
70 Correct 540 ms 56292 KB Output is correct
71 Correct 576 ms 56472 KB Output is correct
72 Correct 559 ms 56264 KB Output is correct
73 Correct 521 ms 56464 KB Output is correct
74 Correct 542 ms 56140 KB Output is correct
75 Correct 525 ms 52432 KB Output is correct
76 Correct 318 ms 48468 KB Output is correct
77 Correct 344 ms 48204 KB Output is correct
78 Correct 354 ms 47180 KB Output is correct
79 Correct 464 ms 52332 KB Output is correct
80 Correct 510 ms 51584 KB Output is correct
81 Correct 548 ms 52048 KB Output is correct
82 Correct 249 ms 46648 KB Output is correct
83 Correct 420 ms 55052 KB Output is correct
84 Correct 446 ms 54220 KB Output is correct
85 Correct 463 ms 54028 KB Output is correct