Submission #556688

#	Time	Username	Problem	Language	Result	Execution time	Memory
556688		Arvin	Sprinkler (JOI22_sprinkler)	C++11	0 / 100	6 ms	9828 KiB

sprinkler

#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){
				for(auto nxt : new_adj[node]){
					int rem = d-getDist(nxt, x);
					if(rem >= 0){
						tree[nxt].update(41-rem, w);
					}
					
//					cout << x << " " << nxt << " -> " << 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 (stderr)

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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17