Submission #732983

#TimeUsernameProblemLanguageResultExecution timeMemory
732983Magikarp4000Bridges (APIO19_bridges)C++17
13 / 100
3073 ms28824 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...