#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
#define vv vector
using namespace std;
const int MAXN = 50*1000+1;
const int MAXM = 2*MAXN;
struct DSU{
int parent[MAXN];
int sz[MAXN];
int rnk[MAXN];
void init(){
FOR(i,MAXN)parent[i] = i;
FOR(i,MAXN)sz[i] = 1;
FOR(i,MAXN)rnk[i] = 1;
}
int find(int a){
if(a == parent[a])return a;
return find(parent[a]);
}
void merge(int a,int b){
if(isSame(a,b))return;
int pa = find(a);
int pb = find(b);
sz[pa] += sz[pb];
parent[pb] = pa;
}
int getSize(int a){
return sz[find(a)];
}
bool isSame(int a,int b){
return find(a) == find(b);
}
};
struct edge{
int ID;
int a,b;
int w;
edge(int id,int aa,int bb,int ww){
ID = id;
a = aa;
b = bb;
w = ww;
}
};
struct query{
int type; // 1 is update, 2 is query
int tm;
int info1; // node for query, edge for update
int info2; // value for either
int id;
query(int t,int a,int b,int c){
type = t;
tm = id = a;
info1 = b;
info2 = c;
}
};
int finalANS[MAXM];
vv<edge> allEdges;
vi rem;
bool edg[MAXM];
void processQueries(vv<query> allQueries){
FOR(i,MAXM)edg[i] = 0;
for(auto e : allQueries){
if(e.type == 1){
edg[e.info1] = 1;
rem.pb(e.info1);
}
}
//cout << "REM CONTENTS : " ;
//for(auto e : rem)cout << e << " ";cout << endl;
//DSU dsu;
//dsu.init();
vv<query> actualQueries;
for(auto e : allQueries){
if(e.type == 2){
actualQueries.pb(e);
}
}
sort(actualQueries.begin(), actualQueries.end(), [&](query a,query b){
return a.info2 >= b.info2;
});
for(auto q : actualQueries){
//cout << "PROCESSING FOR QUERY : " << q.info1 << " " << q.info2 << endl;
DSU dsu;
dsu.init();
FOR(i,allEdges.size()){
if(edg[i])continue;
if(allEdges[i].w < q.info2)continue;
//cout << "PERMEDGE PROCESSED : " << i+1 << endl;
dsu.merge(allEdges[i].a,allEdges[i].b);
}
map<int,int> mp;
for(auto xx : rem){
mp[xx] = allEdges[xx].w;
}
for(auto e : allQueries){
if(e.type == 2)continue;
if(e.tm > q.tm)continue;
//cout << "BLOCK EDGE SEEN : " << e.info1+1 << " " << e.info2 << endl;
mp[e.info1] = e.info2;
}
for(auto x : mp){
if(x.ss >= q.info2){
//cout << "BLOCK EDGE SEEN : " << x.ff+1 << " " << x.ss << endl;
dsu.merge(allEdges[x.ff].a,allEdges[x.ff].b);
}
}
finalANS[q.id] = dsu.getSize(q.info1);
}
for(auto e : allQueries){
if(e.type == 1){
allEdges[e.info1].w = e.info2;
}
}
}
bool quer[MAXM];
int main(){
int n,m;
cin >> n >> m;
FOR(i,m){
int a,b,c;
cin >> a >> b >> c;
a--;b--;
allEdges.pb(edge(i,a,b,c));
}
int q;
cin >> q;
FOR(i,MAXM)finalANS[i] = -1;
int BLOCK = 1;
vv<query> allq;
FOR(i,q){
int a,b,c;
cin >> a >> b >> c;
if(a == 2)quer[i] = 1;
b--;
allq.pb(query(a,i,b,c));
if((i+1)%BLOCK == 0){
processQueries(allq);
allq.clear();
}
}
if(allq.size() > 0)processQueries(allq);
FOR(i,q){
if(quer[i])cout << finalANS[i] << endl;
}
return 0;
}
Compilation message
bridges.cpp: In function 'void processQueries(std::vector<query>)':
bridges.cpp:19:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,n) for(int i=0;i<n;i++)
bridges.cpp:128:7:
FOR(i,allEdges.size()){
~~~~~~~~~~~~~~~~~
bridges.cpp:128:3: note: in expansion of macro 'FOR'
FOR(i,allEdges.size()){
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1144 KB |
Output is correct |
2 |
Correct |
3 ms |
1144 KB |
Output is correct |
3 |
Correct |
2489 ms |
1512 KB |
Output is correct |
4 |
Correct |
1056 ms |
1384 KB |
Output is correct |
5 |
Correct |
1338 ms |
1556 KB |
Output is correct |
6 |
Correct |
1318 ms |
1564 KB |
Output is correct |
7 |
Correct |
1367 ms |
1440 KB |
Output is correct |
8 |
Correct |
1380 ms |
1536 KB |
Output is correct |
9 |
Correct |
1342 ms |
1528 KB |
Output is correct |
10 |
Correct |
1342 ms |
1564 KB |
Output is correct |
11 |
Correct |
1340 ms |
1656 KB |
Output is correct |
12 |
Correct |
1338 ms |
1528 KB |
Output is correct |
13 |
Correct |
1458 ms |
1688 KB |
Output is correct |
14 |
Correct |
1439 ms |
1528 KB |
Output is correct |
15 |
Correct |
1361 ms |
1656 KB |
Output is correct |
16 |
Correct |
1350 ms |
1592 KB |
Output is correct |
17 |
Correct |
1354 ms |
1544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3043 ms |
3628 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3043 ms |
3192 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3031 ms |
4068 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3043 ms |
3628 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1144 KB |
Output is correct |
2 |
Correct |
3 ms |
1144 KB |
Output is correct |
3 |
Correct |
2489 ms |
1512 KB |
Output is correct |
4 |
Correct |
1056 ms |
1384 KB |
Output is correct |
5 |
Correct |
1338 ms |
1556 KB |
Output is correct |
6 |
Correct |
1318 ms |
1564 KB |
Output is correct |
7 |
Correct |
1367 ms |
1440 KB |
Output is correct |
8 |
Correct |
1380 ms |
1536 KB |
Output is correct |
9 |
Correct |
1342 ms |
1528 KB |
Output is correct |
10 |
Correct |
1342 ms |
1564 KB |
Output is correct |
11 |
Correct |
1340 ms |
1656 KB |
Output is correct |
12 |
Correct |
1338 ms |
1528 KB |
Output is correct |
13 |
Correct |
1458 ms |
1688 KB |
Output is correct |
14 |
Correct |
1439 ms |
1528 KB |
Output is correct |
15 |
Correct |
1361 ms |
1656 KB |
Output is correct |
16 |
Correct |
1350 ms |
1592 KB |
Output is correct |
17 |
Correct |
1354 ms |
1544 KB |
Output is correct |
18 |
Execution timed out |
3043 ms |
3628 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |