oj.uz

Submission #588822

# Submission time Handle Problem Language Result Execution time Memory
588822 2022-07-04T06:12:41 Z Tekor Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 77732 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 28500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28444 KB Output is correct
2 Execution timed out 4077 ms 64300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28444 KB Output is correct
2 Execution timed out 4077 ms 64300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28528 KB Output is correct
2 Execution timed out 4086 ms 77732 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 28500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 28500 KB Output isn't correct
2 Halted 0 ms 0 KB -