#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
vector<vector<int>> g;
vector<tuple<int,int,int>> info;
vector<bool> vis;
int dfs(int x, int weight) {
int sum = 1;
vis[x] = true;
for (auto childId : g[x]) {
auto [c1, c2, w] = info[childId];
if (c1 == x) swap(c1,c2);
if (vis[c1]) continue;
if (w < weight) continue;
sum += dfs(c1,weight);
}
return sum;
}
int main() {
int n, m; cin >> n >> m;
g.resize(n + 1);
info.resize(m);
for (int i = 0; i < m; ++i) {
int a, b, w; cin >> a >> b >> w;
g[a].emplace_back(i);
g[b].emplace_back(i);
info[i] = {a,b,w};
}
int q; cin >> q;
for (int i = 0; i < q; ++i) {
int t, a, b; cin >> t >> a >> b;
if (t == 2) {
vis.clear();
vis.resize(n + 1);
cout << dfs(a,b) << "\n";
} else {
auto &[from,to,weight] = info[a - 1];
weight = b;
info[a - 1] = {from,to,weight};
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
49 ms |
652 KB |
Output is correct |
4 |
Correct |
17 ms |
348 KB |
Output is correct |
5 |
Correct |
15 ms |
584 KB |
Output is correct |
6 |
Correct |
14 ms |
604 KB |
Output is correct |
7 |
Correct |
13 ms |
348 KB |
Output is correct |
8 |
Correct |
15 ms |
348 KB |
Output is correct |
9 |
Correct |
14 ms |
344 KB |
Output is correct |
10 |
Correct |
13 ms |
348 KB |
Output is correct |
11 |
Correct |
17 ms |
348 KB |
Output is correct |
12 |
Correct |
13 ms |
564 KB |
Output is correct |
13 |
Correct |
16 ms |
344 KB |
Output is correct |
14 |
Correct |
17 ms |
600 KB |
Output is correct |
15 |
Correct |
16 ms |
604 KB |
Output is correct |
16 |
Correct |
13 ms |
516 KB |
Output is correct |
17 |
Correct |
13 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
183 ms |
9556 KB |
Output is correct |
2 |
Correct |
181 ms |
10280 KB |
Output is correct |
3 |
Correct |
180 ms |
10424 KB |
Output is correct |
4 |
Correct |
344 ms |
10536 KB |
Output is correct |
5 |
Correct |
336 ms |
10512 KB |
Output is correct |
6 |
Execution timed out |
3036 ms |
9424 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
994 ms |
5116 KB |
Output is correct |
2 |
Correct |
2457 ms |
2952 KB |
Output is correct |
3 |
Execution timed out |
3064 ms |
3900 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3076 ms |
9740 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
183 ms |
9556 KB |
Output is correct |
2 |
Correct |
181 ms |
10280 KB |
Output is correct |
3 |
Correct |
180 ms |
10424 KB |
Output is correct |
4 |
Correct |
344 ms |
10536 KB |
Output is correct |
5 |
Correct |
336 ms |
10512 KB |
Output is correct |
6 |
Execution timed out |
3036 ms |
9424 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
49 ms |
652 KB |
Output is correct |
4 |
Correct |
17 ms |
348 KB |
Output is correct |
5 |
Correct |
15 ms |
584 KB |
Output is correct |
6 |
Correct |
14 ms |
604 KB |
Output is correct |
7 |
Correct |
13 ms |
348 KB |
Output is correct |
8 |
Correct |
15 ms |
348 KB |
Output is correct |
9 |
Correct |
14 ms |
344 KB |
Output is correct |
10 |
Correct |
13 ms |
348 KB |
Output is correct |
11 |
Correct |
17 ms |
348 KB |
Output is correct |
12 |
Correct |
13 ms |
564 KB |
Output is correct |
13 |
Correct |
16 ms |
344 KB |
Output is correct |
14 |
Correct |
17 ms |
600 KB |
Output is correct |
15 |
Correct |
16 ms |
604 KB |
Output is correct |
16 |
Correct |
13 ms |
516 KB |
Output is correct |
17 |
Correct |
13 ms |
604 KB |
Output is correct |
18 |
Correct |
183 ms |
9556 KB |
Output is correct |
19 |
Correct |
181 ms |
10280 KB |
Output is correct |
20 |
Correct |
180 ms |
10424 KB |
Output is correct |
21 |
Correct |
344 ms |
10536 KB |
Output is correct |
22 |
Correct |
336 ms |
10512 KB |
Output is correct |
23 |
Execution timed out |
3036 ms |
9424 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |