oj.uz

답안 #624122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624122 2022-08-07T09:54:56 Z Arinoor Sumtree (INOI20_sumtree) C++17
10 / 100
 328 ms 68588 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(ll a, ll b){
	if(a > b)
		return 0;
	if(b < 0 or b >= maxf or a < 0 or a >= maxf or b - a < 0 or b - a >= maxf){
		cout << "-2\n";
		exit(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

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 67772 KB Output is correct
2 Correct 305 ms 67868 KB Output is correct
3 Correct 328 ms 67660 KB Output is correct
4 Correct 294 ms 67888 KB Output is correct
5 Correct 280 ms 63752 KB Output is correct
6 Correct 173 ms 36124 KB Output is correct
7 Correct 177 ms 35912 KB Output is correct
8 Correct 172 ms 35932 KB Output is correct
9 Correct 304 ms 60132 KB Output is correct
10 Correct 289 ms 59980 KB Output is correct
11 Correct 291 ms 60112 KB Output is correct
12 Correct 296 ms 58828 KB Output is correct
13 Correct 287 ms 65340 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 172 ms 35668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 318 ms 68588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 303 ms 64788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 67772 KB Output is correct
2 Correct 305 ms 67868 KB Output is correct
3 Correct 328 ms 67660 KB Output is correct
4 Correct 294 ms 67888 KB Output is correct
5 Correct 280 ms 63752 KB Output is correct
6 Correct 173 ms 36124 KB Output is correct
7 Correct 177 ms 35912 KB Output is correct
8 Correct 172 ms 35932 KB Output is correct
9 Correct 304 ms 60132 KB Output is correct
10 Correct 289 ms 59980 KB Output is correct
11 Correct 291 ms 60112 KB Output is correct
12 Correct 296 ms 58828 KB Output is correct
13 Correct 287 ms 65340 KB Output is correct
14 Incorrect 172 ms 35668 KB Output isn't correct
15 Halted 0 ms 0 KB -