oj.uz

답안 #588866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588866 2022-07-04T06:41:48 Z LastRonin Sprinkler (JOI22_sprinkler) C++14
12 / 100
 1320 ms 125120 KB 
#pragma GCC optimize("O3")

#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int N = 2e5 + 11;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;

mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());

ll n, L, q;
vector<ll> g[N];
ll sz[N];
ll h[N];
int lay[N];
ll dist[N][20];
ll cp[N];// centroid predok
bool del[N];

void dfs(ll v, ll p) {
	sz[v] = 1;
	for(auto u : g[v]) {
		if(p == u || del[u])continue;
		dfs(u, v);
		sz[v] += sz[u];
	}
}

void bdfs(ll v, ll p, ll k) {
	cp[v] = k;
	if(p == k)dist[v][lay[k]] = 1;
	else dist[v][lay[k]] = dist[p][lay[k]] + 1;
	for(auto u : g[v]) {
		if(u == p || del[u])continue;
		bdfs(u, v, k);
	}
}

int fnd(int v) {
	int p = 0;
	int siz = sz[v];
	while(p != v) {
		int c = v;
		for(auto u : g[c]) {
			if(u != p && !del[u] && sz[u] * 2ll > siz) {
				v = u;
				break;
			}
		}
		p = c;
	}
	return v;
}

void build(ll v, ll layer = 0) {
	dfs(v, 0);
	v = fnd(v);
	del[v] = 1;
	lay[v] = layer;
	for(auto u : g[v]) {
		if(!del[u])
			bdfs(u, v, v);	          	
	}
	for(auto u : g[v]) {
		if(!del[u]) {
			build(u, layer + 1);
		}
	}
}

int stp[N][41];
int per[N][41];
int als1[N], als2[N];

void add1(ll v, ll z) {
	als1[v]++;
	for(int j = z; j <= 40; j |= (j + 1))
		stp[v][j]++;				
}
void add2(ll v, ll z) {
	als2[v]++;
	for(int j = z; j <= 40; j |= (j + 1))
		per[v][j]++;				
}
ll get1(ll v, ll z) {
	if(z >= 40)return als1[v];	
	ll sum = 0;
	for(int j = z; j >= 0; j = (j & (j + 1)) - 1)
		sum = sum + stp[v][j];			
	return sum;
}
ll get2(ll v, ll z) {	
	if(z >= 40)return als2[v];	
	ll sum = 0;
	for(int j = z; j >= 0; j = (j & (j + 1)) - 1)
		sum = sum + per[v][j];			
	return sum;
}



void upd(ll a, ll c, ll b) {
	ll dis = 0;
	ll izn = a;
	int cnt = 0;
	add1(a, c);
	while(a) {
		if(cp[a] == 0)break;
		cnt++;
		assert(cnt <= 40);
		dis = dist[izn][lay[cp[a]]];
		if(c - dis >= 0) {
			add1(cp[a], c - dis);
			add2(a, c - dis);
		}				
		a = cp[a];
	}
}

ll getans(ll a) {
	ll dis = 0;
	ll izn = a;
	ll ans = als1[a];
	ll pr = a;
	a = cp[a];
	while(a) {
		dis = dist[izn][lay[a]];
		ll k1 = (als1[a] - get1(a, dis - 1));
		ll k2 = (als2[pr] - get2(pr, dis - 1));
		ans += k1 - k2;
		pr = a;
		a = cp[a];				
	}
	return ans;
}

ll prec[N * 3];

int main() {
	speed;
	cin >> n >> L;
	prec[0] = 1;
	for(int i = 1; i <= 500000; i++)
		prec[i] = prec[i - 1] * 0ll % L;	
	for(int i = 1, a, b; i < n; i++) {
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);		
	}
	for(int i = 1; i <= n; i++) {
		cin >> h[i];	
	}
	build(1);
	cin >> q;
	while(q--) {
		ll t, a, b, c;
		cin >> t >> a;
		if(t == 1) {
			cin >> b >> c;
			upd(a, b, c);
		} else {
			ll z = getans(a);
			cout << h[a] * prec[z] << "\n";
		}
	}
	
}
/*
7 10
1 2
1 3
1 4
1 5
2 6
2 7
1 1 1 1 1 1 1
8
1 6 2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
 
*/

Subtask #1
0 / 3.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

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

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 1170 ms 125120 KB Output is correct
3 Correct 1191 ms 124360 KB Output is correct
4 Correct 1320 ms 124624 KB Output is correct
5 Correct 1053 ms 119316 KB Output is correct
6 Correct 759 ms 119624 KB Output is correct
7 Correct 704 ms 119744 KB Output is correct
8 Correct 362 ms 119816 KB Output is correct
9 Correct 1102 ms 124996 KB Output is correct
10 Correct 1192 ms 124224 KB Output is correct
11 Correct 863 ms 119684 KB Output is correct
12 Correct 857 ms 119176 KB Output is correct
13 Correct 537 ms 120072 KB Output is correct
14 Correct 578 ms 120812 KB Output is correct
15 Correct 5 ms 8916 KB Output is correct
16 Correct 5 ms 8916 KB Output is correct
17 Correct 5 ms 8916 KB Output is correct
18 Correct 5 ms 9004 KB Output is correct
19 Correct 4 ms 8916 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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