/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
struct Dsu {
vector<int> s, p;
vector<pair<int,int>> poop;
int sz;
Dsu(int n){
sz = n;
s.resize(n+1, 1);
p.resize(n+1);
for(int i = 0; i <= n; ++i) p[i] = i;
}
int find(int v){
if(p[v] == v) return v;
return find(p[v]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a != b){
if(s[a] > s[b]){
swap(a, b);
}
s[b] += s[a];
p[a] = b;
poop.pb({a, b});
}else{
poop.pb({-1, -1
});
}
}
void rollback(){
if(poop.size() == 0) return;
if(poop.back().ff == -1){
poop.pop_back();
return;
}
int a = poop.back().ff;
int b = poop.back().ss;
poop.pop_back();
p[a] = a;
s[b] -= s[a];
}
};
int n, m, q;
vector<array<int, 4>> edges;
int S = 300;
void solve(){
cin >> n >> m;
for(int i = 0; i < m; ++i){
int u, v, w; cin >> u >> v >> w;
edges.pb({w, v, u, i});
}
sort(all(edges), greater<array<int, 4>>());
vector<int> pos(m);
vector<int> used(m);
cin >> q;
int pu = 0;
for(int y = 0; y < q; y += S){
for(int i = 0; i < m; ++i) pos[edges[i][3]] = i;
int k = min(q, y+S) - y;
vector<array<int, 3>> upd;
vector<array<int, 4>> qr;
int qq = 0;
for(int j = 0; j < k; ++j){
int t, u, v; cin >> t >> u >> v;
if(t == 1){
--u;
upd.pb({v, u, j});
}else{
qr.pb({v, u, j, qq++});
}
}
vector<int> ans(qq);
Dsu d(n);
// sort(all(upd), greater<array<int, 3>>());
sort(all(qr), greater<array<int, 4>>());
int pu = 0;
for(int l = 0; l < upd.size(); ++l) used[upd[l][1]] = 1;
// for(auto f: qr){
// cout << f[0] << ' ' << f[1] << ' ' << f[2] << '\n';
// }
for(int j = 0; j < qq; ++j){
int w = qr[j][0];
// cout << w << " : q\n" ;
while(pu < edges.size() && edges[pu][0] >= w){
if(used[edges[pu][3]]) ++pu;
else{
d.merge(edges[pu][1], edges[pu][2]);
// cout << edges[pu][3] << " : upd" << '\n';
++pu;
}
}
int roll = 0;
for(int l = int(upd.size()) - 1; l >= 0; --l){
int idx = upd[l][1];
if(used[idx] > 1) continue;
if(upd[l][2] < qr[j][2]){
used[idx] = l + 2;
}
}
for(int l = int(upd.size()) - 1; l >= 0; --l){
int idx = upd[l][1];
if(!(used[idx] == 1 || used[idx] == l + 2)) continue;
if(upd[l][2] < qr[j][2]){
if(upd[l][0] >= w){
++roll;
d.merge(edges[pos[idx]][1], edges[pos[idx]][2]);
}
}else{
if(edges[pos[idx]][0] >= w){
++roll;
d.merge(edges[pos[idx]][1], edges[pos[idx]][2]);
}
}
}
for(int l = int(upd.size()) - 1; l >= 0; --l){
int idx = upd[l][1];
used[idx] = 1;
}
// cout << qr[j][1] << ' ';
ans[qr[j][3]] = d.s[d.find(qr[j][1])];
for(int l = 0; l < roll; ++l){
d.rollback();
}
}
for(int l = 0; l < upd.size(); ++l) used[upd[l][1]] = 0;
for(auto x: ans) cout << x << '\n';
for(auto p: upd){
edges[pos[p[1]]][0] = p[0];
}
sort(all(edges), greater<array<int, 4>>());
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int l = 0; l < upd.size(); ++l) used[upd[l][1]] = 1;
| ~~^~~~~~~~~~~~
street_lamps.cpp:106:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | while(pu < edges.size() && edges[pu][0] >= w){
| ~~~^~~~~~~~~~~~~~
street_lamps.cpp:148:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(int l = 0; l < upd.size(); ++l) used[upd[l][1]] = 0;
| ~~^~~~~~~~~~~~
street_lamps.cpp:74:7: warning: unused variable 'pu' [-Wunused-variable]
74 | int pu = 0;
| ^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:163:15: warning: unused variable 'aa' [-Wunused-variable]
163 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
9160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
