This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 50000;
const int M = 100000;
const int K = 1;
int ea[M+5];
int eb[M+5];
int ec[M+5];
bool changed[M+5];
int qt[M+5];
int qa[M+5];
int qb[M+5];
struct DSU{
int n;
int par[N+5];
int sz[N+5];
void init(int _n){
n = _n;
for(int i=1; i<=n; i++){
par[i] = i;
sz[i] = 1;
}
}
int root(int x){ return (x == par[x] ? x : par[x] = root(par[x])); }
void povezi(int a, int b){
a = root(a);
b = root(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
par[b] = a;
}
} dsu;
int sol[M+5];
const int INF = 1000000007;
vector <int> ima[M+5];
int gde[M+5];
vector <pair <int, int>> unerased;
vector <int> graf[N+5];
bool visited[N+5];
int dfs(int v){
int svi = dsu.sz[v];
visited[v] = 1;
for(auto c : graf[v]) if(!visited[c]) svi += dfs(c);
return svi;
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, m;
cin >> n >> m;
for(int i=1; i<=m; i++){
cin >> ea[i] >> eb[i] >> ec[i];
unerased.push_back({ec[i], i});
}
int qrs;
cin >> qrs;
int qq = 0;
sort(unerased.begin(), unerased.end());
for(int ql=1; ql<=qrs; ql+=K){
int qr = min(qrs, ql+K-1);
dsu.init(n);
vector <pair <int, pair <int, int>>> dvec;
vector <int> ch;
for(int i=ql; i<=qr; i++){
cin >> qt[i] >> qa[i] >> qb[i];
if(qt[i] == 1){
if(!changed[qa[i]]){
ch.push_back(qa[i]);
}
changed[qa[i]] = 1;
}
else{
qq++;
gde[i] = qq;
dvec.push_back({qb[i], {qq, qa[i]}});
}
}
sort(dvec.begin(), dvec.end());
vector <pair <int, pair <int, int>>> vec;
int j = 0;
for(auto c : unerased){
while(j < dvec.size() && c.first >= dvec[j].first){
vec.push_back(dvec[j]);
j++;
}
if(!changed[c.second]) vec.push_back({c.first, {INF, c.second}});
}
while(j < dvec.size()){
vec.push_back(dvec[j]);
j++;
}
reverse(vec.begin(), vec.end());
for(int i=ql; i<=qr; i++){
if(qt[i] == 1) ec[qa[i]] = qb[i];
else{
for(auto c : ch){
if(ec[c] >= qb[i]) ima[gde[i]].push_back(c);
}
}
}
for(auto x : vec){
if(x.second.first == INF) dsu.povezi(ea[x.second.second], eb[x.second.second]);
else{
int ind = x.second.first;
int p = x.second.second;
p = dsu.root(p);
for(auto c : ima[ind]){
int a = dsu.root(ea[c]);
int b = dsu.root(eb[c]);
if(a == b) continue;
graf[a].push_back(b);
graf[b].push_back(a);
}
sol[ind] = dfs(p);
visited[p] = 0;
for(auto c : ima[ind]){
int a = dsu.root(ea[c]);
int b = dsu.root(eb[c]);
graf[a].clear();
graf[b].clear();
visited[a] = visited[b] = 0;
}
}
}
for(int i=ql; i<=qr; i++) if(gde[i]) ima[gde[i]].clear();
vector <pair <int, int>> nv;
vector <pair <int, int>> dv;
for(auto c : ch){
dv.push_back({ec[c], c});
}
sort(dv.begin(), dv.end());
for(auto c : unerased){
while(j < dv.size() && c.first >= dv[j].first){
nv.push_back(c);
j++;
}
if(!changed[c.second]) nv.push_back(c);
}
unerased = nv;
nv.clear();
nv.shrink_to_fit();
for(auto c : ch) changed[c] = 0;
}
for(int i=1; i<=qq; i++) cout << sol[i] << "\n";
return 0;
}
Compilation message (stderr)
bridges.cpp: In function 'int main()':
bridges.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | while(j < dvec.size() && c.first >= dvec[j].first){
| ~~^~~~~~~~~~~~~
bridges.cpp:106:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | while(j < dvec.size()){
| ~~^~~~~~~~~~~~~
bridges.cpp:151:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | while(j < dv.size() && c.first >= dv[j].first){
| ~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |