oj.uz

Submission #624052

# Submission time Handle Problem Language Result Execution time Memory
624052 2022-08-07T07:23:48 Z Arinoor Sumtree (INOI20_sumtree) C++17
10 / 100
 363 ms 150956 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e6 + 10;
const int maxlg = 20;
const int maxf = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int n, ans, fact[maxf], invfact[maxf];
int val[maxn], tag[maxn];
int par[maxn][maxlg], sz[maxn], st[maxn], ed[maxn], tme = 1;
ll fenC[maxn], fenS[maxn], fenP[maxn];
vector<int> G[maxn];

int add(int a, int b){
	int c = a + b;
	if(c >= mod) c -= mod;
	if(c < 0) c += mod;
	return c;
}

int mul(int a, int b){
	return 1ll * a * b % mod;
}

int pwr(int a, int b){
	int res = 1;
	for(; b; b >>= 1, a = mul(a, a)) if(b & 1) res = mul(res, a);
	return res;
}

int inv(int a){
	return pwr(a, mod - 2);
}

int C(ll a, ll b){
	if(a > b) return 0;
  	if(a < 0) return 0;
	return mul(fact[b], mul(invfact[a], invfact[b - a]));
}

void update_fact(){
	fact[0] = 1;
	for(int i = 1; i < maxf; i ++)
		fact[i] = mul(fact[i - 1], i);
	invfact[maxf - 1] = inv(fact[maxf - 1]);
	for(int i = maxf - 2; ~i; i --)
		invfact[i] = mul(invfact[i + 1], i + 1);
}

void add(ll *fen, int i, ll x){
	for(; i <= n; i += i & -i)
		fen[i] += x;
}

ll get(ll *fen, int i){
	ll res = 0;
	for(; i; i -= i & -i)
		res += fen[i];
	return res;
}

ll get(ll *fen, int l, int r){
	return get(fen, r) - get(fen, l - 1);
}

void dfs(int v, int p = 0){
	par[v][0] = p;
	for(int i = 1; i < maxlg and par[v][i - 1]; i ++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	st[v] = tme;
	sz[v] = 1;
	for(int u : G[v]){
		if(u ^ p){
			tme ++;
			dfs(u, v);
			sz[v] += sz[u];
		}
	}
	ed[v] = tme;
}

int get_val(int v){
	ll cnt = sz[v] - get(fenC, st[v] + 1, ed[v]);
	ll sum = tag[v] - get(fenS, st[v] + 1, ed[v]);
	return C(cnt - 1, cnt + sum - 1);
}

int find(int v){
	int x = get(fenP, st[v]);
	for(int i = maxlg - 1; ~i; i --){
		int u = par[v][i];
		if(!u) continue;
		if(get(fenP, st[u]) == x)
			v = u;
	}
	return par[v][0];
}

int main(){
	ios;
	update_fact();
	int r;
	cin >> n >> r;
	for(int i = 0; i < n - 1; i ++){
		int u, v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	memset(tag, -1, sizeof tag);
	tag[1] = r;
	dfs(1);
	add(fenP, st[1] + 1, 1); add(fenP, ed[1] + 1, -1);
	fill_n(val, maxn, 1);
	ans = val[1] = get_val(1);
	cout << ans << '\n';
	int q; cin >> q;
	int Cnt = 0;
	while(q--){
		int t, v;
		cin >> t >> v;
		if(t == 1){
			int x; cin >> x;
			tag[v] = x;
			val[v] = get_val(v);
			if(val[v])
				ans = mul(ans, val[v]);
			else
				Cnt ++;
			int p = find(v);
			if(inv(val[p]))
				ans = mul(ans, inv(val[p]));
			else
				Cnt --;
			ll cnt = sz[v] - get(fenC, st[v] + 1, ed[v]);
			add(fenC, st[v], cnt);
			ll sum = tag[v] - get(fenS, st[v] + 1, ed[v]);
			add(fenS, st[v], sum);
			val[p] = get_val(p);
			if(val[p])
				ans = mul(ans, val[p]);
			else
				Cnt ++;
			add(fenP, st[v] + 1, 1); add(fenP, ed[v] + 1, -1);
		}
		else{
			if(inv(val[v]))
				ans = mul(ans, inv(val[v]));
			else
				Cnt --;
			val[v] = 1;
			int p = find(v);
			if(inv(val[p]))
				ans = mul(ans, inv(val[p]));
			else
				Cnt --;
			ll cnt = sz[v] - get(fenC, st[v] + 1, ed[v]);
			add(fenC, st[v], -cnt);
			ll sum = tag[v] - get(fenS, st[v] + 1, ed[v]);
			add(fenS, st[v], -sum);
			val[p] = get_val(p);
			if(val[p])
				ans = mul(ans, val[p]);
			else
				Cnt ++;
			add(fenP, st[v] + 1, -1); add(fenP, ed[v] + 1, 1);
			tag[v] = -1;
		}
		if(Cnt)
			cout << "0\n";
		else
			cout << ans << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 71588 KB Output is correct
2 Correct 177 ms 71660 KB Output is correct
3 Correct 185 ms 71664 KB Output is correct
4 Correct 175 ms 71608 KB Output is correct
5 Correct 144 ms 67648 KB Output is correct
6 Correct 32 ms 40084 KB Output is correct
7 Correct 36 ms 39860 KB Output is correct
8 Correct 34 ms 39784 KB Output is correct
9 Correct 169 ms 64060 KB Output is correct
10 Correct 149 ms 63900 KB Output is correct
11 Correct 147 ms 63984 KB Output is correct
12 Correct 150 ms 62676 KB Output is correct
13 Correct 155 ms 69236 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 363 ms 139504 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 185 ms 71588 KB Output is correct
2 Correct 177 ms 71660 KB Output is correct
3 Correct 185 ms 71664 KB Output is correct
4 Correct 175 ms 71608 KB Output is correct
5 Correct 144 ms 67648 KB Output is correct
6 Correct 32 ms 40084 KB Output is correct
7 Correct 36 ms 39860 KB Output is correct
8 Correct 34 ms 39784 KB Output is correct
9 Correct 169 ms 64060 KB Output is correct
10 Correct 149 ms 63900 KB Output is correct
11 Correct 147 ms 63984 KB Output is correct
12 Correct 150 ms 62676 KB Output is correct
13 Correct 155 ms 69236 KB Output is correct
14 Incorrect 30 ms 39424 KB Output isn't correct
15 Halted 0 ms 0 KB -