大了MLE,小了CE
查看原帖
大了MLE,小了CE
326254
LonginusMonkey楼主2023/7/14 19:57

请问我该怎么调整数组大小。还是说代码本身无法通过

还有就是一般数组开最大能开多大比如char int等等。望详细讲解

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int v, next;
}edge[200100];
int fa[200100], head[200100], w[200100], w_new[200100], cnt, tot = 1, N, M, R, P, tree[400100], deep[200100], size[400100], son[200100], top[200100], id[200100], tag[400100];
void add(int u, int v) {edge[tot].v = v;edge[tot].next = head[u];head[u] = tot++;}
void build(int l, int r, int index) {
	if(l == r) {
		tree[index] = w_new[l] % P;
		return;
	}
	int mid = l+r >> 1;
	build(l, mid, index*2);
	build(mid+1, r, index*2+1);
	tree[index] = tree[index*2] + tree[index*2+1];
	tree[index] %= P;
}
int push_down(int l, int r, int index) {
	tag[index*2] += tag[index],tag[index*2]%=P;
	tag[index*2+1] += tag[index],tag[index*2+1]%=P;
	tree[index] += (r-l+1) * tag[index],tree[index]%=P;
	tag[index]=0;
}
void update(int l, int r, int index, int left, int right, int x) {
	push_down(l, r, index);
	if(left <= l && r <= right) {
		tag[index]+=x;
		tag[index] %= P;
		return;
	}
	if(l > right || r < left) {
		return;
	}
	int mid = l+r>>1;
	update(l, mid, index*2, left, right, x);
	update(mid+1, r, index*2+1, left, right, x);
	push_down(l, mid, index*2);
	push_down(mid+1, r, index*2+1);
	tree[index] = tree[index*2] + tree[index*2+1];
	tree[index] %= P;
}
int query(int l, int r, int index, int left, int right) {
	push_down(l, r, index);
	if(left <= l && r <= right) {
		return tree[index] % P;
	}
	if(left > r || right < l) {
		return 0;
	}
	int mid = l + r >> 1;
	return (query(l, mid, index*2, left, right) + query(mid+1, r, index*2+1, left, right)) % P;
}
void input() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> R >> P;
	for(int i = 1; i <= N; ++i) {cin >> w[i];}
	for(int i = 1, u, v; i < N; ++i) {cin >> u >> v;add(u, v); add(v, u);}
}
void dfs1(int index, int back, int depth) {
	fa[index] = back;
	size[index] = 1;
	deep[index] = depth;
	for(int i = head[index]; i; i = edge[i].next) {
		int to = edge[i].v;
		if(to == back) continue;
		dfs1(to, index, depth+1);
		if(son[index] == 0 || size[son[index]] < size[to])
			son[index] = to;
		size[index] += size[to];
	}
}
void dfs2(int index, int back, int topx) {
	id[index] = ++cnt;
	w_new[cnt] = w[index];
	top[index] = topx;
	if(!son[index]) return;
	dfs2(son[index], index, topx);
	for(int i = head[index]; i; i = edge[i].next) {
		int t = edge[i].v;
		if(t == back || t == son[index]) continue;
		dfs2(t, index, t);
	}
}
void update_tree(int index, int k) {
	update(1,N,1,id[index],id[index]+size[index]-1, k);
}
int q_tree(int index) {
	return query(1,N,1,id[index],id[index]+size[index]-1);
}
void update_range(int x, int y, int z) {
	while(top[x]!=top[y]) {
		if(deep[top[x]] < deep[top[y]]) swap(x, y);
		update(1,N,1,id[top[x]],id[x],z);
		x = fa[top[x]];
	}
	if(deep[x] > deep[y]) swap(x, y);
	update(1,N,1,id[x],id[y],z);
}
int q_range(int x, int y, int z) {
	int ans = 0;
	while(top[x]!=top[y]) {
		if(deep[top[x]] < deep[top[y]]) swap(x, y);
		ans += query(1,N,1,id[top[x]],id[x]);
		ans %= P;
		x = fa[top[x]];
	}
	if(deep[x] > deep[y]) swap(x, y);
	ans += query(1,N,1,id[x],id[y]);
	return ans%P;
}
signed main() {
	input();
	dfs1(R, 0, 1);
	dfs2(R, 0, R);
	build(1, N, 1);
	while(M--) {
		int k, x, y, z; cin >> k;
		switch(k) {
			case 1:cin >> x >> y >> z; update_range(x, y, z); break;
			case 2:cin >> x >> y; cout << q_range(x, y, z) << endl; break;
			case 3:cin >> x >> y; update_tree(x, y); break;
			case 4:cin >> x; cout << q_tree(x) << endl; break;
		}
	}
	return 0;
}

MLE https://www.luogu.com.cn/record/115545186 CE https://www.luogu.com.cn/record/115544068

2023/7/14 19:57
加载中...