Submission #588850

#	Time	Username	Problem	Language	Result	Execution time	Memory
588850		Tekor	Sprinkler (JOI22_sprinkler)	C++17	9 / 100	308 ms	39004 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define f first
#define s second
#define pii pair <int,int>
#define en '\n'
void boos() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int N = 4e5 + 100;
const int bl = 400;
vector <int> g[N],tt[N];
ll a[N],d[N][2],L;
int n;
/*
4 7
1 2
2 3
3 4
1
1
1
1
6
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
*/
void solve() {
	cin >> n >> L;
	for(int i = 1;i <= n;i++) {
		d[i][0] = 1;
		d[i][1] = 1;
	}
	for(int i = 1;i < n;i++) {
		int x,y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	for(int i = 1;i <= n;i++) {
		for(auto to : g[i]) {
			if(g[to].size() > bl)tt[i].pb(to);
		}
	}
	for(int i = 1;i <= n;i++)cin >> a[i];
	int q;
	cin >> q;
	for(int i = 1;i <= q;i++) {
		int typ;
		cin >> typ;
		if(typ == 1) {
			int x,dist;
			ll w;
			cin >> x >> dist >> w;
			a[x] = (a[x] * w) % L;
			if(dist == 0)continue;
			if(g[x].size() <= bl) {
				for(auto to : g[x]) {
					a[to] = (a[to] * w) % L;
				}
			}else {
				d[x][1] = (d[x][1] * w) % L;
			}
		}else {
			int x;
			cin >> x;
			ll ans = a[x];
			for(auto to : tt[x]) {
				ans = (ans * d[to][1]) % L;
			}
			cout << ans << en;
		}
	}
}

int main() {
	boos();
	int ttt;
	ttt = 1;
	while(ttt--) {
		solve();
	}
}

• Subtask 1: 0 / 3
• Subtask 2: 9 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17