제출 #588822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588822		Tekor	Sprinkler (JOI22_sprinkler)	C++17	0 / 100	4086 ms	77732 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 = 316;
vector <int> g[N];
pair <int,pair <int,pair <int,ll> > > c[N];
ll a[N],L;
ll d[N][2];
map <int,bool> was[N];
int n;
void dfs(int v,int p) {
	for(auto to : g[v]) {
		if(to == p)continue;
		d[to][0] = (d[to][0] * d[v][1]) % L;
		d[v][0] = (d[v][0] * d[to][1]) % L;
		dfs(to,v);
	}
	a[v] = (a[v] * d[v][0]) % L;
	a[v] = (a[v] * d[v][1]) % L;
}
/*
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;
		was[x][y] = 1;
		was[y][x] = 1;
		g[x].pb(y);
		g[y].pb(x);
	}
	for(int i = 1;i <= n;i++)cin >> a[i];
	int q;
	cin >> q;
	int l = 1;
	for(int i = 1;i <= q;i++) {
		cin >> c[i].f;
		if(c[i].f == 1)cin >> c[i].s.f >> c[i].s.s.f >> c[i].s.s.s;
		else cin >> c[i].s.f;
		if(i % bl == 0 || i == q) {
			for(int j = l;j <= i;j++) {
				if(c[j].f == 1) {
					d[c[j].s.f][c[j].s.s.f] = (d[c[j].s.f][c[j].s.s.f] * c[j].s.s.s) % L;
					continue;
				}
				ll ans = a[c[j].s.f];
				//cout << ans << " ";
				for(int h = l;h < j;h++) {
					if(c[h].f == 1 && c[h].s.s.f >= (int)(c[j].s.f != c[h].s.f) && (c[j].s.f == c[h].s.f || was[c[j].s.f].count(c[h].s.f))) {
						ans = (ans * c[h].s.s.s) % L;
						//cout << h << " -- " << c[h].s.s.s << en;
					}
				}
				cout << ans << en;
			}
			dfs(1,-1);
			for(int j = 1;j <= n;j++) {
				d[j][0] = 1;
				d[j][1] = 1;
			}
			l = i;
		}
	}
}

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

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