oj.uz

Submission #556703

# Submission time Handle Problem Language Result Execution time Memory
556703 2022-05-03T17:40:41 Z Arvin Sprinkler (JOI22_sprinkler) C++11
0 / 100
 4000 ms 260208 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;
const int maxQ = 4e5 + 5;

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)];	
}

vector<pair<int, int>> v[maxN];

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;
	
	int idx = 0;
	ll val[q];
	
	while(q--){
		int t;
		cin >> t;
		
		if(t == 1){
			int x, d, w;
			cin >> x >> d >> w;
			
			x--;
			
			val[idx] = w;
			int node = x, prv = -1;
			while(node != -1){
				int rem = d-getDist(node, x);
				if(rem >= 0){
					v[node].push_back({rem, idx});
//					tree[node].update(41-rem, w);
				}
				
//				cout << x << " " << node << " -> " << rem << " " << w << "\n";
				
				prv = node;
				node = parent[node];
			}
			
			idx++;
		} else if(t == 2){
			int x;
			cin >> x;
			
			x--;
			
			ll ans = h[x];
			
			set<int> st;
			map<int, int> mp;
			
			int node = x;
			while(node != -1){
				int d = getDist(node, x);
				
				if(d <= 40){
					for(auto p : v[node]){
						if(!st.count(p.second) && d <= p.first){
							st.insert(p.second);
							ans *= val[p.second];
							ans %= l;
						}
						if(mp.find(p.second) != mp.end()){
							assert(d >= mp[p.second]);
						}
						
						mp[p.second] = d;
					}
				}
				
//				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:186:18: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
  186 |    int node = x, prv = -1;
      |                  ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Runtime error 22 ms 30344 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 2375 ms 121152 KB Output is correct
3 Correct 2395 ms 126808 KB Output is correct
4 Correct 3249 ms 130984 KB Output is correct
5 Correct 2416 ms 122916 KB Output is correct
6 Correct 1665 ms 122644 KB Output is correct
7 Correct 1688 ms 122880 KB Output is correct
8 Execution timed out 4069 ms 115196 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 2375 ms 121152 KB Output is correct
3 Correct 2395 ms 126808 KB Output is correct
4 Correct 3249 ms 130984 KB Output is correct
5 Correct 2416 ms 122916 KB Output is correct
6 Correct 1665 ms 122644 KB Output is correct
7 Correct 1688 ms 122880 KB Output is correct
8 Execution timed out 4069 ms 115196 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Runtime error 726 ms 260208 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14548 KB Output is correct
2 Runtime error 725 ms 250048 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Runtime error 22 ms 30344 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -