#include <bits/stdc++.h>
using namespace std;
#define int long long
int dis[200005], h[200005];
vector<int> adjl[200005];
int n, l, a, b;
int kali(int a, int b) {
return ((a%l)*(b%l))%l;
}
int pangkat(int a, int n) {
if (n == 0) return 1;
if (n == 1) return a%l;
int temp = pangkat(a, n/2);
temp = kali(temp, temp);
if (n%2 == 1) return kali(temp, a);
return temp;
}
void bfs(int start, int d, int w) {
queue<int> q;
memset(dis, -1, sizeof(dis));
q.push(start);
dis[start] = 0;
h[start] = kali(h[start], w);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto i: adjl[cur]) {
if (dis[i] == -1) {
dis[i] = dis[cur]+1;
if (dis[i] <= d) {
h[i] = kali(h[i], w);
if (dis[i] < d) {
q.push(i);
}
}
}
}
}
}
map<vector<int>, int> freq;
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> l;
for (int i = 1; i < n; i++) {
cin >> a >> b;
adjl[a].push_back(b);
adjl[b].push_back(a);
}
for (int i = 1; i <= n; i++) cin >> h[i];
int q, t, x, d, w;
cin >> q;
while (q--) {
cin >> t;
if (t == 1) {
cin >> x >> d >> w;
freq[{x, d, w}]++;
}
else if (t == 2) {
for (auto i: freq) {
if (i.second > 0) {
// cout << i.first[0] << " " << i.first[1] << " " << i.first[2] << " " << i.second << endl;
if (i.first[1] == 0) h[i.first[0]] = kali(h[i.first[0]], pangkat(i.first[2], i.second));
else if (i.first[1] == 1) {
h[i.first[0]] = kali(h[i.first[0]], pangkat(i.first[2], i.second));
for (auto j: adjl[i.first[0]]) h[j] = kali(h[j], pangkat(i.first[2], i.second));
}
else bfs(i.first[0], i.first[1], pangkat(i.first[2], i.second));
freq[{i.first[0], i.first[1], i.first[2]}] = 0;
}
}
cin >> x;
cout << h[x]%l << endl;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
20 ms |
6660 KB |
Output is correct |
5 |
Correct |
25 ms |
6656 KB |
Output is correct |
6 |
Correct |
28 ms |
6612 KB |
Output is correct |
7 |
Correct |
27 ms |
6612 KB |
Output is correct |
8 |
Correct |
28 ms |
6680 KB |
Output is correct |
9 |
Correct |
6 ms |
5076 KB |
Output is correct |
10 |
Correct |
6 ms |
5076 KB |
Output is correct |
11 |
Correct |
6 ms |
5084 KB |
Output is correct |
12 |
Correct |
6 ms |
5044 KB |
Output is correct |
13 |
Correct |
6 ms |
5076 KB |
Output is correct |
14 |
Correct |
11 ms |
6612 KB |
Output is correct |
15 |
Correct |
11 ms |
6628 KB |
Output is correct |
16 |
Correct |
11 ms |
6652 KB |
Output is correct |
17 |
Correct |
12 ms |
6616 KB |
Output is correct |
18 |
Correct |
13 ms |
6648 KB |
Output is correct |
19 |
Correct |
9 ms |
6484 KB |
Output is correct |
20 |
Correct |
8 ms |
6484 KB |
Output is correct |
21 |
Correct |
8 ms |
6484 KB |
Output is correct |
22 |
Correct |
8 ms |
6484 KB |
Output is correct |
23 |
Correct |
8 ms |
6484 KB |
Output is correct |
24 |
Correct |
8 ms |
6484 KB |
Output is correct |
25 |
Correct |
8 ms |
6484 KB |
Output is correct |
26 |
Correct |
8 ms |
6600 KB |
Output is correct |
27 |
Correct |
9 ms |
6600 KB |
Output is correct |
28 |
Correct |
8 ms |
6484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Execution timed out |
4059 ms |
14732 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Execution timed out |
4059 ms |
14732 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6484 KB |
Output is correct |
2 |
Execution timed out |
4038 ms |
15316 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Execution timed out |
4037 ms |
15444 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
20 ms |
6660 KB |
Output is correct |
5 |
Correct |
25 ms |
6656 KB |
Output is correct |
6 |
Correct |
28 ms |
6612 KB |
Output is correct |
7 |
Correct |
27 ms |
6612 KB |
Output is correct |
8 |
Correct |
28 ms |
6680 KB |
Output is correct |
9 |
Correct |
6 ms |
5076 KB |
Output is correct |
10 |
Correct |
6 ms |
5076 KB |
Output is correct |
11 |
Correct |
6 ms |
5084 KB |
Output is correct |
12 |
Correct |
6 ms |
5044 KB |
Output is correct |
13 |
Correct |
6 ms |
5076 KB |
Output is correct |
14 |
Correct |
11 ms |
6612 KB |
Output is correct |
15 |
Correct |
11 ms |
6628 KB |
Output is correct |
16 |
Correct |
11 ms |
6652 KB |
Output is correct |
17 |
Correct |
12 ms |
6616 KB |
Output is correct |
18 |
Correct |
13 ms |
6648 KB |
Output is correct |
19 |
Correct |
9 ms |
6484 KB |
Output is correct |
20 |
Correct |
8 ms |
6484 KB |
Output is correct |
21 |
Correct |
8 ms |
6484 KB |
Output is correct |
22 |
Correct |
8 ms |
6484 KB |
Output is correct |
23 |
Correct |
8 ms |
6484 KB |
Output is correct |
24 |
Correct |
8 ms |
6484 KB |
Output is correct |
25 |
Correct |
8 ms |
6484 KB |
Output is correct |
26 |
Correct |
8 ms |
6600 KB |
Output is correct |
27 |
Correct |
9 ms |
6600 KB |
Output is correct |
28 |
Correct |
8 ms |
6484 KB |
Output is correct |
29 |
Correct |
2 ms |
4948 KB |
Output is correct |
30 |
Execution timed out |
4059 ms |
14732 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |