#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+1] = {a, b, c};
}
cin>>q;
if(n <= 1000 && m <= 1000 && q <= 1000){
for(int i=0;i<q;i++){
int t; cin>>t;
if(t == 1){
int br, w; cin>>br>>w;
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;
for(auto& x : edges[b]) if(x.ff == a && x.ss == c) x.ss = w;
} 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({0, 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";
}
}
}
}
# |
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 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
24 ms |
7388 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
5988 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
63 ms |
12540 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
24 ms |
7388 KB |
Output isn't correct |
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 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |