oj.uz

Submission #557579

# Submission time Handle Problem Language Result Execution time Memory
557579 2022-05-05T13:58:53 Z Arvin Sprinkler (JOI22_sprinkler) C++11
0 / 100
 805 ms 108600 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
 
const int maxN = 2e5 + 5;
const int maxD = 45;
const int logN = log2(maxN)+1;
 
ll l;

vector<int> adj[maxN];
ll val[maxN][maxD];
int level[maxN];
int parent[maxN];
 
void dfs(int curNode, int prvNode = 0){
	parent[curNode] = prvNode;
	
	for(auto nxt : adj[curNode]){
		if(nxt != prvNode){
			level[nxt] = level[curNode]+1;
			dfs(nxt, curNode);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
	int n;
	cin >> n >> l;
	
	for(int x=0;x<n-1;x++){
		int a, b;
		cin >> a >> b;
		
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	ll h[n];
	for(int x=0;x<n;x++){
		cin >> h[x];
	}
	
	level[0] = 0;
	dfs(0, -1);
	
	fill(val[0], val[maxN], 1);
	
	int q;
	cin >> q;
	
	while(q--){
		int t;
		cin >> t;
		
		if(t == 1){
			int x, d, w;
			cin >> x >> d >> w;
			
			x--;
			
			int node = x;
			while(node != -1 && d >= 0){
				val[node][d] *= w;
				val[node][d] %= l;
				
				d--;
				node = parent[node];
			}
			if(d > 0){
				for(int x=0;x<min(d, maxD);x++){
					val[0][x] *= w;
					val[0][x] %= l;
				}
			}
			
		} else if(t == 2){
			int x;
			cin >> x;
			
			x--;
			
			ll ans = h[x];
			int d = 0;
			int node = x;
			
			while(node != -1 && d <= 40){
				ans *= val[node][d];
				ans %= l;
				
				if(node != 0 && d < 40) ans *= val[node][d+1];
				ans %= l;
				
				d++;
				node = parent[node];
			}
			
			cout << ans << "\n";
		} else {
			assert(false);
		}
	}
    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 75340 KB Output is correct
2 Correct 31 ms 75444 KB Output is correct
3 Correct 32 ms 75352 KB Output is correct
4 Incorrect 33 ms 75456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 75340 KB Output is correct
2 Correct 627 ms 96288 KB Output is correct
3 Correct 409 ms 92004 KB Output is correct
4 Correct 592 ms 102056 KB Output is correct
5 Correct 525 ms 94044 KB Output is correct
6 Correct 411 ms 94160 KB Output is correct
7 Correct 351 ms 94528 KB Output is correct
8 Correct 324 ms 94764 KB Output is correct
9 Correct 801 ms 108600 KB Output is correct
10 Correct 393 ms 107440 KB Output is correct
11 Incorrect 592 ms 94744 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 75340 KB Output is correct
2 Correct 627 ms 96288 KB Output is correct
3 Correct 409 ms 92004 KB Output is correct
4 Correct 592 ms 102056 KB Output is correct
5 Correct 525 ms 94044 KB Output is correct
6 Correct 411 ms 94160 KB Output is correct
7 Correct 351 ms 94528 KB Output is correct
8 Correct 324 ms 94764 KB Output is correct
9 Correct 801 ms 108600 KB Output is correct
10 Correct 393 ms 107440 KB Output is correct
11 Incorrect 592 ms 94744 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 75428 KB Output is correct
2 Correct 765 ms 104796 KB Output is correct
3 Correct 699 ms 101520 KB Output is correct
4 Correct 670 ms 102576 KB Output is correct
5 Correct 585 ms 93016 KB Output is correct
6 Correct 373 ms 93260 KB Output is correct
7 Correct 382 ms 93612 KB Output is correct
8 Correct 289 ms 93700 KB Output is correct
9 Correct 805 ms 101880 KB Output is correct
10 Correct 642 ms 104508 KB Output is correct
11 Correct 649 ms 93260 KB Output is correct
12 Correct 650 ms 93780 KB Output is correct
13 Correct 415 ms 94384 KB Output is correct
14 Correct 454 ms 95588 KB Output is correct
15 Incorrect 31 ms 75416 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 75412 KB Output is correct
2 Incorrect 766 ms 103160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 75340 KB Output is correct
2 Correct 31 ms 75444 KB Output is correct
3 Correct 32 ms 75352 KB Output is correct
4 Incorrect 33 ms 75456 KB Output isn't correct
5 Halted 0 ms 0 KB -