#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;
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;
}
pair<pii,pii> group(int u, int v){
int ou = p[u];
int ov = p[v];
while (p[u] != p[p[u]]) p[u] = p[p[u]];
while (p[v] != p[p[v]]) p[v] = p[p[v]];
int x = p[u];
int y = p[v];
if (x==y) return {{-1,-1},{-1,-1}};
if (ssize[x] < ssize[y]) swap(x,y);
ssize[x] += ssize[y];
p[y] = x;
return {{u,v},{ou,ov}};
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(cnt,0,sizeof(cnt));
int n,m;
cin >> n >> m;
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;
}
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;
}
gsize = sqrt(q);
vector<int> curre;
vector<int> cvis;
vector<int> ans;
int cidx;
int res[q];
// 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 = i*gsize; j < min(q,(i+1)*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);
}
}
for (int j = 0; j < m; j++) if (cnt[j] != i+1) curre.pb(j);
sort(curre.begin(),curre.end(),comp);
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";*/
for (int j = 0; j < n; j++){
p[j] = j;
ssize[j] = 1;
}
cidx = 0;
stack<pair<pii,pii>> upd;
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++;
}
// cout << " 2 ";
for (int k = ans[j]-1; k >= i*gsize; k--){
if (all[k].a == 2) continue;
if (cnt[all[k].b] != q+i+1){
cnt[all[k].b] = q+i+1;
if (all[k].w < all[ans[j]].w) continue;
// cout << all[k].b << " ";
upd.push(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 << " ";
upd.push(group(edges[all[k].b].a,edges[all[k].b].b));
}
// cout << '\n';
int c = all[ans[j]].b;
int prev = p[c];
while (p[c] != p[p[c]]) p[c] = p[p[c]];
res[ans[j]] = ssize[p[c]];
p[c] = prev;
pair<pii,pii> temp;
while (upd.sz() > 0){
temp = upd.top();
upd.pop();
u = temp.f.f;
v = temp.f.s;
if (u == -1) continue;
if (ssize[p[u]] < ssize[p[v]]){
ssize[p[v]] -= ssize[p[u]];
p[p[u]] = p[u];
} else {
ssize[p[u]] -= ssize[p[v]];
p[p[v]] = p[v];
}
p[u] = temp.s.f;
p[v] = temp.s.s;
}
}
for (int j : cvis) edges[all[j].b].w = all[j].w;
}
for (int i =0; i < q; i++){
if (all[i].a == 1) continue;
cout << res[i] << "\n";
}
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int j = 0; j < ans.sz(); j++){
| ~~^~~~~~~~~~
bridges.cpp:107:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | while (cidx < curre.sz() && edges[curre[cidx]].w >= all[ans[j]].w){
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
2652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2094 ms |
4100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1443 ms |
3820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3034 ms |
5004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2094 ms |
4100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
2652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
