oj.uz

Submission #624120

# Submission time Handle Problem Language Result Execution time Memory
624120 2022-08-07T09:51:39 Z Arinoor Sumtree (INOI20_sumtree) C++17
10 / 100
 472 ms 143012 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 = 19;
const int maxf = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int n, 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(int a, ll b){
	if(a > b)
		return 0;
	return mul(fact[b], mul(invfact[a], invfact[b - a]));
}

void update_fact(){
	fact[0] = invfact[0] = 1;
	for(int i = 1; i < maxf; i ++){
		fact[i] = mul(fact[i - 1], i);
		invfact[i] = inv(fact[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){
	int 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);
	}
	dfs(1);
	memset(tag, -1, sizeof tag);
	tag[1] = r;
	add(fenP, st[1] + 1, 1); add(fenP, ed[1] + 1, -1);
	for(int i = 2; i <= n; i ++)
		val[i] = 1;
	val[1] = get_val(1);
	int ans = 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 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);
			add(fenP, st[v] + 1, 1); add(fenP, ed[v] + 1, -1);
			int p = find(v);
			if(inv(val[p]))
				ans = mul(ans, inv(val[p]));
			else
				Cnt --;
			val[p] = get_val(p);
			if(val[p])
				ans = mul(ans, val[p]);
			else
				Cnt ++;
		}
		else{
			if(inv(val[v]))
				ans = mul(ans, inv(val[v]));
			else
				Cnt --;
			val[v] = 1;
			int 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);
			add(fenP, st[v] + 1, -1); add(fenP, ed[v] + 1, 1);
			int p = find(v);
			if(inv(val[p]))
				ans = mul(ans, inv(val[p]));
			else
				Cnt --;
			val[p] = get_val(p);
			if(val[p])
				ans = mul(ans, val[p]);
			else
				Cnt ++;
			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 296 ms 67688 KB Output is correct
2 Correct 303 ms 67804 KB Output is correct
3 Correct 311 ms 67764 KB Output is correct
4 Correct 308 ms 67776 KB Output is correct
5 Correct 292 ms 63804 KB Output is correct
6 Correct 171 ms 36084 KB Output is correct
7 Correct 177 ms 35952 KB Output is correct
8 Correct 173 ms 35872 KB Output is correct
9 Correct 286 ms 60064 KB Output is correct
10 Correct 306 ms 59916 KB Output is correct
11 Correct 294 ms 60008 KB Output is correct
12 Correct 287 ms 58812 KB Output is correct
13 Correct 284 ms 65328 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 35568 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 361 ms 143012 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 472 ms 131524 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 296 ms 67688 KB Output is correct
2 Correct 303 ms 67804 KB Output is correct
3 Correct 311 ms 67764 KB Output is correct
4 Correct 308 ms 67776 KB Output is correct
5 Correct 292 ms 63804 KB Output is correct
6 Correct 171 ms 36084 KB Output is correct
7 Correct 177 ms 35952 KB Output is correct
8 Correct 173 ms 35872 KB Output is correct
9 Correct 286 ms 60064 KB Output is correct
10 Correct 306 ms 59916 KB Output is correct
11 Correct 294 ms 60008 KB Output is correct
12 Correct 287 ms 58812 KB Output is correct
13 Correct 284 ms 65328 KB Output is correct
14 Incorrect 171 ms 35568 KB Output isn't correct
15 Halted 0 ms 0 KB -