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;
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define sz size
const int mxN = 1e5;
struct edge {
int a,b,w;
};
edge edges[mxN];
edge all[mxN];
int p[mxN];
int ssize[mxN];
int cnt[mxN];
int gsize;
stack<int> upd;
bool comp(int a, int b){
return (edges[a].w > edges[b].w);
}
bool comp2(int a, int b){
return all[a].w > all[b].w;
}
int gp(int a){
while (p[a] != a) a = p[a];
return a;
}
void group(int u, int v){
u = gp(u);
v = gp(v);
if (u==v) return;
if (ssize[u] < ssize[v]) swap(u,v);
ssize[u] += ssize[v];
p[v] = u;
upd.push(v);
return;
}
void reset(int a){
int c;
while (upd.sz() > a){
c = upd.top();
upd.pop();
ssize[p[c]] -= ssize[c];
p[c] = c;
}
}
struct cmp {
bool operator() (int a, int b) const {
if (edges[a].w == edges[b].w) return a < b;
return edges[a].w > edges[b].w;
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(cnt,0,sizeof(cnt));
int n,m;
cin >> n >> m;
set<int,cmp> alle;
for (int i =0; i < m; i++){
cin >> edges[i].a >> edges[i].b >> edges[i].w;
edges[i].a -= 1;
edges[i].b -= 1;
alle.insert(i);
}
int q;
cin >> q;
for (int i = 0; i < q; i++){
cin >> all[i].a >> all[i].b >> all[i].w;
all[i].b -= 1;
}
for (int i =0; i < n; i++){
p[i] = i;
ssize[i] = 1;
}
gsize = sqrt(q);
vector<int> curre;
vector<int> cvis;
vector<int> ans;
int cidx;
int res[q];
for (int i =0; i < q; i++) res[i] = -1;
// cout <<"GISZE " << gsize << "\n";
for (int i =0; i < (int) ceil((double) q/gsize); i++){
curre.clear();
ans.clear();
cvis.clear();
/* cout << "W: ";
for (int j = 0; j < m; j++) cout << edges[j].w << " ";
cout << '\n';*/
for (int j = min(q,(i+1)*gsize)-1; j >= i*gsize; j--){
if (all[j].a == 1 && cnt[all[j].b] != i+1){
cnt[all[j].b] = i+1;
cvis.pb(j);
} else {
ans.pb(j);
}
}
// cout << alle.sz() << ": ";
// for (auto it = alle.begin(); it != alle.end(); it++) cout << (*it) << " ";
// cout << "\n";
for (auto it = alle.begin(); it != alle.end(); it++) if (cnt[(*it)] != i+1) curre.pb(*it);
// for (int j = 0; j < m; j++) if (cnt[alle[j]] != i+1) curre.pb(alle[j]);
sort(ans.begin(),ans.end(),comp2);
/*cout << i << ":\n";
for (int j : curre) cout << j << " ";
cout << '\n';
for (int j : ans) cout << j << " ";
cout << "\n";*/
cidx = 0;
int u,v;
for (int j = 0; j < ans.sz(); j++){
//Adding on non-changing edges
// cout << j <<" - ";
while (cidx < curre.sz() && edges[curre[cidx]].w >= all[ans[j]].w){
// cout << curre[cidx] << " ";
group(edges[curre[cidx]].a,edges[curre[cidx]].b);
cidx++;
}
int osize = upd.sz();
// cout << " 2 ";
for (int k = ans[j]-1; k >= i*gsize; k--){
if (all[k].a == 2 || cnt[all[k].b] == q+i+1) continue;
cnt[all[k].b] = q+i+1;
if (all[k].w < all[ans[j]].w) continue;
// cout << all[k].b << " ";
group(edges[all[k].b].a,edges[all[k].b].b);
}
// cout << " 3 ";
for (int k : cvis){
if (cnt[all[k].b] == q+i+1 || edges[all[k].b].w < all[ans[j]].w){
cnt[all[k].b] = i+1;
continue;
}
// cout << all[k].b << " ";
group(edges[all[k].b].a,edges[all[k].b].b);
}
// cout << '\n';
int c = all[ans[j]].b;
c = gp(c);
res[ans[j]] = ssize[c];
reset(osize);
}
reset(0);
for (int j : cvis){
alle.erase(all[j].b);
edges[all[j].b].w = all[j].w;
alle.insert(all[j].b);
}
}
for (int i =0; i < q; i++){
if (all[i].a == 1) continue;
cout << res[i] << "\n";
if (res[i] == -1) while (true) continue;
}
return 0;
}
Compilation message (stderr)
bridges.cpp: In function 'void reset(int)':
bridges.cpp:51:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
51 | while (upd.sz() > a){
| ~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:129:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int j = 0; j < ans.sz(); j++){
| ~~^~~~~~~~~~
bridges.cpp:132:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | while (cidx < curre.sz() && edges[curre[cidx]].w >= all[ans[j]].w){
| ~~~~~^~~~~~~~~~~~
bridges.cpp:128:13: warning: unused variable 'u' [-Wunused-variable]
128 | int u,v;
| ^
bridges.cpp:128:15: warning: unused variable 'v' [-Wunused-variable]
128 | int u,v;
| ^
# | 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... |