제출 #276063

#제출 시각아이디문제언어결과실행 시간메모리
276063groeneprof다리 (APIO19_bridges)C++14
13 / 100
3059 ms8184 KiB
#include <bits/stdc++.h> #define P(a) do{if(debug) cout<<a<<endl;} while(false) #define H(a) P(#a<<": "<<a) #define FR(i,a,b) for(int i = (a); i<(b); i++) #define F(i,n) FR(i,0,n) const int debug = 0; using namespace std; vector<pair<int,int> > edges; vector<int> weights; int n, m, q; vector<vector<pair<int,int> > > graph; vector<int> par; int root(int a){ if(par[a] == a) return a; return par[a] = root(par[a]); } void merge(int a, int b){ if(rand()%2) swap(a,b); par[root(a)] = root(b); } void kruskal(){ vector<pair<int,pair<int,int> > > sorted(m); F(i,m){ sorted[i] = {weights[i], edges[i]}; } sort(sorted.rbegin(),sorted.rend()); par.resize(n); F(i,n) par[i] = i; graph.assign(n,{}); for(auto e : sorted){ if(root(e.second.first)!=root(e.second.second)){ H(e.second.first); H(e.second.second); H(e.first); H(root(e.second.first)); H(root(e.second.second)); merge(e.second.first,e.second.second); graph[e.second.first].push_back({e.second.second, e.first}); graph[e.second.second].push_back({e.second.first, e.first}); } } } int dfs(int u, int p, int w){ int a = 1; for(pair<int,int> v : graph[u]) if(v.first!=p && v.second>=w){ a+=dfs(v.first,u,w); } return a; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m; edges.resize(m); weights.resize(m); F(i,m){ cin>>edges[i].first>>edges[i].second>>weights[i]; edges[i].first--; edges[i].second--; } kruskal(); cin>>q; F(i,q){ int type; cin>>type; if(type==1){ int a, b; cin>>a>>b; a--; weights[a] = b; kruskal(); } else{ int a, b; cin>>a>>b; a--; cout<<dfs(a,a,b)<<endl; } } 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...