This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n'
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
const int MAXN = 1e5+1;
int n,m,q;
UM<int,vector<int>> v[MAXN];
vector<pair<PII,PII>> e;
bool z[MAXN];
signed main() {
OPTM;
cin >> n >> m;
FOR(i,0,m) {
int a,b,w; cin >> a >> b >> w;
v[a][b].PB(w);
v[b][a].PB(w);
e.PB({{a,b},{v[a][b].size()-1,v[b][a].size()-1}});
}
cin >> q;
FOR(i,0,q) {
int t; cin >> t;
if (t == 1) {
int idx,w; cin >> idx >> w;
idx--;
int a = e[idx].F.F, b = e[idx].F.S, c = e[idx].S.F, d = e[idx].S.S;
v[a][b][c] = v[b][a][d] = w;
}
else {
int s,w; cin >> s >> w;
FOR(i,1,n+1) z[i] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int k = q.front(); q.pop();
if (z[k]) continue;
z[k] = 1;
FORX(u,v[k]) {
FORX(y,u.S) if (y >= w) q.push(u.F);
}
}
int res = 0;
FOR(i,1,n+1) res += z[i];
cout << res << ln;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |