Submission #977466

#TimeUsernameProblemLanguageResultExecution timeMemory
977466dubabubaBridges (APIO19_bridges)C++14
0 / 100
3095 ms11988 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; #define ff first #define ss second #define MP make_pair const int mxn = 2e5 + 10; vector<pair<int, pii>> edges; vector<pii> adj[mxn]; int n, m, q; int solve(int st, int we) { bool vis[n + 1]; memset(vis, 0, sizeof vis); queue<int> q; q.push(st); // cout << st << ' ' << we << ": "; int ret = 0; while(q.size()) { int u = q.front(); q.pop(); if(vis[u]) continue; // cout << u << ' '; vis[u] = 1; ret++; for(pii p : adj[u]) { int v = p.ff; int w = p.ss; if(vis[v]) continue; if(w < we) continue; q.push(v); } } // cout << endl; return ret; } int main() { cin >> n >> m; for(int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back(MP(v, w)); adj[v].push_back(MP(u, w)); edges.push_back(MP(w, MP(u, v))); } cin >> q; for(int i = 0; i < q; i++) { int t, s, w; cin >> t >> s >> w; // for(int i = 1; i <= n; i++) // for(pii p : adj[i]) // cout << i << " -> " << p.ff << " = " << p.ss << endl; if(t == 2) cout << solve(s, w) << endl; else { int d = edges[s - 1].ff; int u = edges[s - 1].ss.ff; int v = edges[s - 1].ss.ss; for(pii &p : adj[u]) if(p == MP(v, d)) p.ss = w; for(pii &p : adj[v]) if(p == MP(u, d)) p.ss = w; } } 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...