Submission #569130

#TimeUsernameProblemLanguageResultExecution timeMemory
569130aryan12Bridges (APIO19_bridges)C++17
13 / 100
3086 ms10860 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; vector<array<int, 2> > g[N]; vector<array<int, 3> > edges(N * 2); vector<bool> vis(N); int dfs(int node, int wt) { vis[node] = true; int ans = 1; for(auto [to, idx]: g[node]) { int cur_wt = edges[idx][2]; if(cur_wt >= wt && !vis[to]) { ans += dfs(to, wt); } } return ans; } void Solve() { int n, m; cin >> n >> m; for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, i}); g[v].push_back({u, i}); 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; edges[edge_idx][2] = wt; } else { int node, start_wt; cin >> node >> start_wt; for(int j = 0; j <= n; j++) { vis[j] = false; } // cout << "hello\n"; // cout << "node = " << node << ", start_wt = " << start_wt << "\n"; cout << dfs(node, start_wt) << "\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...