oj.uz

Submission #556697

# Submission time Handle Problem Language Result Execution time Memory
556697 2022-05-03T17:11:18 Z Arvin Sprinkler (JOI22_sprinkler) C++11
21 / 100
 2954 ms 135500 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;

struct Fenwick {
	ll tree[maxD];
	
	void reset(){
		fill(tree, tree+maxD, 1);
	}
	
	void update(int pos, int val){
		pos++;
		
		while(pos < maxD){
			tree[pos] *= val;
			tree[pos] %= l;
			pos += pos&(-pos);
		}
	}
	
	ll query(int pos){
		pos++;
		
		ll ans = 1;
		while(pos > 0){
			ans *= tree[pos];
			ans %= l;
			pos -= pos&(-pos);
		}
		return ans;
	}
};

vector<int> adj[maxN], new_adj[maxN];
Fenwick tree[maxN];
bool exist[maxN];
int parent[maxN], level[maxN], sz[maxN];
int ancestor[logN][maxN];

void dfs(int curNode, int prvNode){
	sz[curNode] = 1;
	
	for(auto nxt : adj[curNode]){
		if(nxt != prvNode && exist[nxt]){
			dfs(nxt, curNode);
			sz[curNode] += sz[nxt];	
		}
	}	
}

void dfs2(int curNode, int prvNode = 0){
	level[curNode] = level[prvNode]+1;
	ancestor[0][curNode] = prvNode;
	
	for(int x=1;x<logN;x++){
		ancestor[x][curNode] = ancestor[x-1][ancestor[x-1][curNode]];
	}
	
	for(auto nxt : adj[curNode]){
		if(nxt != prvNode){
			dfs2(nxt, curNode);
		}
	}	
}

int centroid(int curNode){
	dfs(curNode, curNode);
	int sum = sz[curNode];
	
	int root = curNode;
	bool found = false;
	while(!found){
		found = true;
		for(auto nxt : adj[root]){
			if(exist[nxt] && sz[nxt] <= sz[root] && sz[nxt] > sum/2){
				root = nxt;
				found = false;
				break;
			}
		}
	}
	return root;
}

int build(int curNode){
	int root = centroid(curNode);
	exist[root] = false;
	
	for(auto nxt : adj[root]){
		if(exist[nxt]){
			int nxtRoot = build(nxt);
			parent[nxtRoot] = root;
			new_adj[root].push_back(nxtRoot);
		}
	}
	return root;
}

int getLCA(int a, int b){
	if(level[a] > level[b]) swap(a, b);
	
	for(int x=logN-1;x>=0;x--){
		if(level[a] <= level[b]-(1 << x)){
			b = ancestor[x][b];
		}
	}
	
	if(a == b) return a;
	
	for(int x=logN-1;x>=0;x--){
		if(ancestor[x][a] != ancestor[x][b]){
			a = ancestor[x][a];
			b = ancestor[x][b];
		}
	}
	
	return ancestor[0][a];
}

int getDist(int a, int b){
	return level[a] + level[b] - 2*level[getLCA(a, b)];	
}

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];
		tree[x].reset();
		exist[x] = true;
	}
	
	parent[build(0)] = -1;
	
	level[0] = -1;
	dfs2(0);
	
//	for(int x=0;x<n;x++){
//		cout << parent[x] << " ";
//	}cout << "\n";
	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, prv = -1;
			while(node != -1){
				int rem = d-getDist(node, x);
				if(rem >= 0){
					tree[node].update(41-rem, w);
				}
				
//				cout << x << " " << node << " -> " << rem << " " << w << "\n";
				
				prv = node;
				node = parent[node];
			}
		} else if(t == 2){
			int x;
			cin >> x;
			
			x--;
			
			ll ans = h[x];
			
			int node = x;
			while(node != -1){
				int d = getDist(node, x);
				
				if(d <= 40){
					ans *= tree[node].query(41-d);
					ans %= l;
				}
				
//				cout << level[node] << " " << node << " -> " << d << " " << ans << " " << tree[node].query(41-d) << "\n";
				node = parent[node];
			}
			
			cout << ans << "\n";
		} else {
			assert(false);
		}
	}
    return 0;
}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:178:18: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
  178 |    int node = x, prv = -1;
      |                  ^~~

Subtask #1
0 / 3.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 2182 ms 119280 KB Output is correct
3 Correct 1907 ms 119136 KB Output is correct
4 Correct 2883 ms 129880 KB Output is correct
5 Correct 1922 ms 119252 KB Output is correct
6 Correct 1170 ms 116612 KB Output is correct
7 Correct 954 ms 118704 KB Output is correct
8 Correct 399 ms 115496 KB Output is correct
9 Correct 2889 ms 135500 KB Output is correct
10 Correct 2765 ms 134308 KB Output is correct
11 Correct 2029 ms 117764 KB Output is correct
12 Correct 1973 ms 116252 KB Output is correct
13 Correct 347 ms 118764 KB Output is correct
14 Correct 425 ms 118760 KB Output is correct
15 Correct 451 ms 108448 KB Output is correct
16 Correct 478 ms 112864 KB Output is correct
17 Correct 517 ms 114416 KB Output is correct
18 Correct 5 ms 9852 KB Output is correct
19 Correct 5 ms 9852 KB Output is correct
20 Correct 5 ms 9812 KB Output is correct
21 Correct 6 ms 9812 KB Output is correct
22 Correct 5 ms 9812 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 2182 ms 119280 KB Output is correct
3 Correct 1907 ms 119136 KB Output is correct
4 Correct 2883 ms 129880 KB Output is correct
5 Correct 1922 ms 119252 KB Output is correct
6 Correct 1170 ms 116612 KB Output is correct
7 Correct 954 ms 118704 KB Output is correct
8 Correct 399 ms 115496 KB Output is correct
9 Correct 2889 ms 135500 KB Output is correct
10 Correct 2765 ms 134308 KB Output is correct
11 Correct 2029 ms 117764 KB Output is correct
12 Correct 1973 ms 116252 KB Output is correct
13 Correct 347 ms 118764 KB Output is correct
14 Correct 425 ms 118760 KB Output is correct
15 Correct 451 ms 108448 KB Output is correct
16 Correct 478 ms 112864 KB Output is correct
17 Correct 517 ms 114416 KB Output is correct
18 Correct 5 ms 9852 KB Output is correct
19 Correct 5 ms 9852 KB Output is correct
20 Correct 5 ms 9812 KB Output is correct
21 Correct 6 ms 9812 KB Output is correct
22 Correct 5 ms 9812 KB Output is correct
23 Correct 7 ms 9808 KB Output is correct
24 Incorrect 1988 ms 119284 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 2804 ms 131672 KB Output is correct
3 Correct 2863 ms 128592 KB Output is correct
4 Correct 2881 ms 129064 KB Output is correct
5 Correct 1984 ms 116348 KB Output is correct
6 Correct 1095 ms 116000 KB Output is correct
7 Correct 889 ms 115884 KB Output is correct
8 Correct 394 ms 114368 KB Output is correct
9 Correct 2878 ms 128020 KB Output is correct
10 Correct 2954 ms 131132 KB Output is correct
11 Correct 1972 ms 116068 KB Output is correct
12 Correct 2116 ms 116524 KB Output is correct
13 Correct 1069 ms 115148 KB Output is correct
14 Correct 1124 ms 116528 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 6 ms 9812 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 6 ms 9812 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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