oj.uz

답안 #964657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964657 2024-04-17T09:48:23 Z yellowtoad Sprinkler (JOI22_sprinkler) C++17
0 / 100
 470 ms 63828 KB 
#include <iostream>
#include <vector>
#define f first
#define s second
#define int long long
using namespace std;
 
int n, mod, a[200050], cnt, test, p[200050];
pair<int,int> rng[200050], grp[200050];
vector<int> edge[200050], d[200050], node[200050];
bool up;
 
void dfs(int u, int v, int depth) {
	p[u] = v;
	rng[u].f = ++cnt;
	grp[u] = {depth,d[depth].size()};
	d[depth].push_back(u);
	for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs(edge[u][i],u,depth+1);
	rng[u].s = cnt;
}
 
void build(int i, int id, int x, int y) {
	if (x == y) {
		node[i][id] = a[d[i][x]];
		return;
	}
	int mid = (x+y)/2;
	build(i,id*2,x,mid);
	build(i,id*2+1,mid+1,y);
	node[i][id] = 1;
}
 
void update(int i, int id, int x, int y, int l, int r, int val) {
	if ((l <= rng[d[i][x]].f) && (rng[d[i][y]].f <= r)) {
		(node[i][id] *= val) %= mod;
		return;
	}
	if ((rng[d[i][x]].f < l) || (r < rng[d[i][y]].f)) return;
	int mid = (x+y)/2;
	(node[i][id*2] *= node[i][id]) %= mod;
	(node[i][id*2+1] *= node[i][id]) %= mod;
	node[i][id] = 1;
	update(i,id*2,x,mid,l,r,val);
	update(i,id*2+1,mid+1,y,l,r,val);
}

int query(int i, int id, int x, int y, int pos) {
	if (x == y) return node[i][id];
	int mid = (x+y)/2;
	(node[i][id*2] *= node[i][id]) %= mod;
	(node[i][id*2+1] *= node[i][id]) %= mod;
	node[i][id] = 1;
	if (pos <= mid) return query(i,id*2,x,mid,pos);
	else return query(i,id*2+1,mid+1,y,pos);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> mod;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) cin >> a[i];
	dfs(1,0,1);
	for (int i = 1; i <= n; i++) {
		if (d[i].size()) {
			node[i].resize(d[i].size()*4+10);
			build(i,1,0,d[i].size()-1);
		}
	}
	cin >> test;
	while (test--) {
		int type, u, dis, val, depth;
		cin >> type;
		if (type == 1) {
			cin >> u >> dis >> val;
			depth = grp[u].f+dis;
			up = 0;
			while (depth >= grp[u].f) {
				if (d[depth].size()) update(depth,1,0,d[depth].size()-1,rng[u].f,rng[u].s,val);
				if ((up) && (p[u])) u = p[u];
				up = 1-up;
				depth--;
			}
		} else {
			cin >> u;
			cout << query(grp[u].f,1,0,d[grp[u].f].size()-1,grp[u].s) << "\n";
		}
	}
}

Compilation message

sprinkler.cpp: In function 'void dfs(long long int, long long int, long long int)':
sprinkler.cpp:18:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs(edge[u][i],u,depth+1);
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Incorrect 5 ms 21188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 21084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 21084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 21084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Incorrect 470 ms 63828 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Incorrect 5 ms 21188 KB Output isn't correct
3 Halted 0 ms 0 KB -