oj.uz

답안 #972761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972761 2024-05-01T06:34:17 Z happy_node Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 104784 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=2e5+5;
int N,L,Q;
int A[MX], B[MX], H[MX];
vector<int> adj[MX];

int par[MX];
ll w[MX][50]; // w and w inverse

void dfs(int v, int p) {
	par[v]=p;
	for(auto u:adj[v]) {
		if(u==p) continue;
		dfs(u,v);
	}
}

void upd(int v, int d, int x) {
	while(d>=0 && v!=0) {
		w[v][d]*=x;
		w[v][d]%=L;
		v=par[v];
		d--;
	}
}

int que(int v) {
	int d=0,p=-1;
	ll res=1;
	while(d>=0 && v!=0) {
		for(int i=d;i<=40;i++) {
			if(par[v]!=0 && i-1>=d+1) continue;
			res*=w[v][i];
			res%=L;
		}
		d++;
		p=v;
		v=par[v];
	}
	return res;
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	for(int i=0;i<MX;i++)
		for(int d=0;d<=41;d++)
			w[i][d]=1;

	cin>>N>>L;
	for(int i=0;i<N-1;i++) {
		cin>>A[i]>>B[i];
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}	

	for(int i=1;i<=N;i++) cin>>w[i][0];

	dfs(1,0);

	cin>>Q;
	for(int i=1;i<=Q;i++) {
		int t;
		cin>>t;

		if(t==1) {
			int x,d,w;
			cin>>x>>d>>w;
			upd(x,d,w);
		} else {
			int x;
			cin>>x;
			cout<<que(x)<<'\n';
		}
	}	
}

Compilation message

sprinkler.cpp: In function 'int que(int)':
sprinkler.cpp:31:10: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   31 |  int d=0,p=-1;
      |          ^

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 84756 KB Output is correct
2 Correct 13 ms 84572 KB Output is correct
3 Correct 13 ms 84756 KB Output is correct
4 Correct 14 ms 84828 KB Output is correct
5 Correct 14 ms 84856 KB Output is correct
6 Correct 15 ms 84828 KB Output is correct
7 Correct 16 ms 84828 KB Output is correct
8 Correct 17 ms 84728 KB Output is correct
9 Correct 14 ms 84824 KB Output is correct
10 Correct 13 ms 84696 KB Output is correct
11 Correct 13 ms 84572 KB Output is correct
12 Correct 13 ms 84568 KB Output is correct
13 Correct 16 ms 84572 KB Output is correct
14 Correct 13 ms 84568 KB Output is correct
15 Correct 13 ms 84572 KB Output is correct
16 Correct 14 ms 84668 KB Output is correct
17 Correct 14 ms 84804 KB Output is correct
18 Correct 14 ms 84572 KB Output is correct
19 Correct 14 ms 84756 KB Output is correct
20 Correct 16 ms 84572 KB Output is correct
21 Correct 13 ms 84572 KB Output is correct
22 Correct 13 ms 84572 KB Output is correct
23 Correct 13 ms 84640 KB Output is correct
24 Correct 14 ms 84576 KB Output is correct
25 Correct 14 ms 84800 KB Output is correct
26 Correct 14 ms 84764 KB Output is correct
27 Correct 14 ms 84568 KB Output is correct
28 Correct 13 ms 84576 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 84568 KB Output is correct
2 Correct 2519 ms 104388 KB Output is correct
3 Correct 470 ms 104784 KB Output is correct
4 Execution timed out 4058 ms 100740 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 84568 KB Output is correct
2 Correct 2519 ms 104388 KB Output is correct
3 Correct 470 ms 104784 KB Output is correct
4 Execution timed out 4058 ms 100740 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 84568 KB Output is correct
2 Execution timed out 4025 ms 102108 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 84568 KB Output is correct
2 Execution timed out 4062 ms 100552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 84756 KB Output is correct
2 Correct 13 ms 84572 KB Output is correct
3 Correct 13 ms 84756 KB Output is correct
4 Correct 14 ms 84828 KB Output is correct
5 Correct 14 ms 84856 KB Output is correct
6 Correct 15 ms 84828 KB Output is correct
7 Correct 16 ms 84828 KB Output is correct
8 Correct 17 ms 84728 KB Output is correct
9 Correct 14 ms 84824 KB Output is correct
10 Correct 13 ms 84696 KB Output is correct
11 Correct 13 ms 84572 KB Output is correct
12 Correct 13 ms 84568 KB Output is correct
13 Correct 16 ms 84572 KB Output is correct
14 Correct 13 ms 84568 KB Output is correct
15 Correct 13 ms 84572 KB Output is correct
16 Correct 14 ms 84668 KB Output is correct
17 Correct 14 ms 84804 KB Output is correct
18 Correct 14 ms 84572 KB Output is correct
19 Correct 14 ms 84756 KB Output is correct
20 Correct 16 ms 84572 KB Output is correct
21 Correct 13 ms 84572 KB Output is correct
22 Correct 13 ms 84572 KB Output is correct
23 Correct 13 ms 84640 KB Output is correct
24 Correct 14 ms 84576 KB Output is correct
25 Correct 14 ms 84800 KB Output is correct
26 Correct 14 ms 84764 KB Output is correct
27 Correct 14 ms 84568 KB Output is correct
28 Correct 13 ms 84576 KB Output is correct
29 Correct 13 ms 84568 KB Output is correct
30 Correct 2519 ms 104388 KB Output is correct
31 Correct 470 ms 104784 KB Output is correct
32 Execution timed out 4058 ms 100740 KB Time limit exceeded
33 Halted 0 ms 0 KB -