#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define int long long
#define ff first
#define ss second
template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }
const int mod = 1e9+7;
const int N = 1e5+5;
int n, m, q, mn[N];
vector<pair<int, int>> edges[N];
array<int, 3> tt[N];
int dis[N];
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=0;i<m;i++){
int a, b, c; cin>>a>>b>>c;
edges[a].pb({b, c}), edges[b].pb({a, c});
tt[i] = {a, b, c};
} cin>>q;
if(n <= 1000 && m <= 1000 && q <= 10000){
while(q--){
int t; cin>>t;
if(t == 1){
int br, w; cin>>br>>w, br--;
int a = tt[br][0], b = tt[br][1], c = tt[br][2]; tt[br][2] = w;
for(auto& x : edges[a]) if(x.ff == b && x.ss == c) { x.ss = w; break; }
for(auto& x : edges[b]) if(x.ff == a && x.ss == c) { x.ss = w; break; }
} else {
int u, w; cin>>u>>w;
for(int i=1;i<=n;i++) mn[i] = -mod;
priority_queue<pair<int, int>> qq;
mn[u] = mod; qq.push({mod, u});
while(!qq.empty()){
auto u = qq.top(); qq.pop();
if(mn[u.ss] > u.ff) continue;
for(auto x : edges[u.ss])
if(umax(mn[x.ff], min(mn[u.ss], x.ss))) qq.push({mn[x.ff], x.ff});
} int rr = 0;
for(int i=1;i<=n;i++) if(mn[i] >= w) rr++;
cout<<rr<<"\n";
}
}
} else assert(0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
176 ms |
2788 KB |
Output is correct |
4 |
Correct |
7 ms |
2636 KB |
Output is correct |
5 |
Correct |
25 ms |
2708 KB |
Output is correct |
6 |
Correct |
19 ms |
2636 KB |
Output is correct |
7 |
Correct |
28 ms |
2700 KB |
Output is correct |
8 |
Correct |
37 ms |
2692 KB |
Output is correct |
9 |
Correct |
30 ms |
2832 KB |
Output is correct |
10 |
Correct |
21 ms |
2708 KB |
Output is correct |
11 |
Correct |
21 ms |
2636 KB |
Output is correct |
12 |
Correct |
21 ms |
2636 KB |
Output is correct |
13 |
Correct |
59 ms |
2696 KB |
Output is correct |
14 |
Correct |
59 ms |
2692 KB |
Output is correct |
15 |
Correct |
53 ms |
2700 KB |
Output is correct |
16 |
Correct |
29 ms |
2708 KB |
Output is correct |
17 |
Correct |
33 ms |
2692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
32 ms |
12372 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
21 ms |
10444 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
67 ms |
20588 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
32 ms |
12372 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
176 ms |
2788 KB |
Output is correct |
4 |
Correct |
7 ms |
2636 KB |
Output is correct |
5 |
Correct |
25 ms |
2708 KB |
Output is correct |
6 |
Correct |
19 ms |
2636 KB |
Output is correct |
7 |
Correct |
28 ms |
2700 KB |
Output is correct |
8 |
Correct |
37 ms |
2692 KB |
Output is correct |
9 |
Correct |
30 ms |
2832 KB |
Output is correct |
10 |
Correct |
21 ms |
2708 KB |
Output is correct |
11 |
Correct |
21 ms |
2636 KB |
Output is correct |
12 |
Correct |
21 ms |
2636 KB |
Output is correct |
13 |
Correct |
59 ms |
2696 KB |
Output is correct |
14 |
Correct |
59 ms |
2692 KB |
Output is correct |
15 |
Correct |
53 ms |
2700 KB |
Output is correct |
16 |
Correct |
29 ms |
2708 KB |
Output is correct |
17 |
Correct |
33 ms |
2692 KB |
Output is correct |
18 |
Runtime error |
32 ms |
12372 KB |
Execution killed with signal 6 |
19 |
Halted |
0 ms |
0 KB |
- |