Submission #569119

#TimeUsernameProblemLanguageResultExecution timeMemory
569119aryan12Bridges (APIO19_bridges)C++17
0 / 100
3043 ms19408 KiB
#include <bits/stdc++.h> using namespace std; #define int long long mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); const int N = 5e4 + 5; set<array<int, 2> > g[N]; vector<bool> vis(N); int dfs(int node, int wt, int par) { vis[node] = true; int ans = 1; for(auto [to, cur_wt]: g[node]) { if(cur_wt >= wt && !vis[to]) { ans += dfs(to, wt, node); } } return ans; } void Solve() { int n, m; cin >> n >> m; vector<array<int, 3> > edges(m + 1); for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; g[u].insert({v, w}); g[v].insert({u, w}); edges[i] = {u, v, w}; } int q; cin >> q; for(int i = 1; i <= q; i++) { int command; cin >> command; if(command == 1) { int edge_idx, wt; cin >> edge_idx >> wt; int prev_wt = edges[edge_idx][2]; int u = edges[edge_idx][0], v = edges[edge_idx][1]; g[u].erase({v, prev_wt}); g[u].insert({v, wt}); g[v].erase({u, prev_wt}); g[v].insert({u, wt}); edges[edge_idx][2] = wt; } else { int node, start_wt; cin >> node >> start_wt; for(int i = 0; i <= n; i++) { vis[i] = false; } // cout << "hello\n"; // cout << "node = " << node << ", start_wt = " << start_wt << "\n"; cout << dfs(node, start_wt, -1) << "\n"; } } } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }
#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...