#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
int n,m;
int L[mxn];
int R[mxn];
int W[mxn];
int vis[mxn]={};
vector<int> v;
int parent[mxn];
int sz[mxn];
vector<int> adj[mxn];
int block=400;
int findrep(int u) {
return parent[u]==u ? u : (parent[u]=findrep(parent[u]));
}
void unite(int u,int v) {
u=findrep(u);
v=findrep(v);
if(sz[u]>sz[v]) swap(u,v);
if(u!=v) {
parent[u]=v;
sz[v]+=sz[u];
}
}
struct query {
int u,w,id,t,id2;
query(int _,int __,int ___,int ____,int qind) : u(_), w(__), id(___),t(____),id2(qind) {};
};
int dfs(int cur,int k) {
vis[cur]=k;
int ans=sz[cur];
for(int u:adj[cur]) {
if(vis[u]!=k) {
ans+=dfs(u,k);
}
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
int U,V,d;
scanf("%d%d%d",&U,&V,&d);
L[i]=U;
R[i]=V;
W[i]=d;
v.push_back(i);
}
int q;
scanf("%d",&q);
vector<query> Q;
int K=0;
for(int i=1;i<=q;i++) {
int t,u,w;
scanf("%d%d%d",&t,&u,&w);
K+=t-1;
Q.push_back(query(u,w,i,t,K));
}
int res[mxn];
int mq[mxn]={};
int dontuse[mxn]={};
for(int i=1;i<=m;i++)mq[i]=W[i];
int vin=1;
sort(v.begin(),v.end(),[](int a,int b) {
return W[a]>W[b];
});
for(int i=0;i<q;i+=block) {
for(int j=1;j<=n;j++) {
parent[j]=j;
sz[j]=1;
}
vector<query> cur1;
vector<query> cur2;
for(int j=i;j<min(q,i+block);j++) {
if(Q[j].t==1) {
dontuse[Q[j].u]=1;
cur2.push_back(Q[j]);
}
else cur1.push_back(Q[j]);
}
sort(cur1.begin(),cur1.end(),[](query a,query b) {
return a.w > b.w;
});
int lp=0;
for(int j=0;j<cur1.size();j++) {
while(lp<m && W[v[lp]]>=cur1[j].w) {
if(dontuse[v[lp]]!=1) {
unite(L[v[lp]],R[v[lp]]);
}
lp++;
}
for(int k=0;k<cur2.size();k++) {
if(cur2[k].id > cur1[j].id ) break;
mq[cur2[k].u]=cur2[k].w;
}
for(int k=0;k<cur2.size();k++) {
if(mq[cur2[k].u]>=cur1[j].w) {
int u=L[cur2[k].u];
int v=R[cur2[k].u];
u=findrep(u);
v=findrep(v);
adj[u].push_back(v);
adj[v].push_back(u);
}
}
int tm=dfs(findrep(cur1[j].u),vin++);
res[cur1[j].id2]=tm;
for(int k=0;k<cur2.size();k++) {
if(mq[cur2[k].u]>=cur1[j].w) {
int u=L[cur2[k].u];
int v=R[cur2[k].u];
u=findrep(u);
v=findrep(v);
adj[u].clear();
adj[v].clear();
}
mq[cur2[k].u]=W[cur2[k].u];
}
}
for(int j=0;j<cur2.size();j++) {
W[cur2[j].u]=mq[cur2[j].u]=cur2[j].w;
}
vector<int> tmp;
vector<int> ups;
for(int j=0;j<m;j++) {
if(dontuse[v[j]]!=1) tmp.push_back(v[j]);
else ups.push_back(v[j]);
}
sort(ups.begin(),ups.end(),[](int a,int b) {
return W[a] > W[b];
});
v.clear();
for(int j=0,k=0; j< tmp.size() || k< ups.size(); ) {
if(j==tmp.size()) v.push_back(ups[k++]);
else if(k==ups.size()) v.push_back(tmp[j++]);
else if(W[tmp[j]]>=W[ups[k]]) v.push_back(tmp[j++]);
else v.push_back(ups[k++]);
}
for(int j=0;j<cur2.size();j++) dontuse[cur2[j].u]=0;
}
for(int i=1;i<=K;i++)cout<<res[i]<<endl;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:119:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int j=0;j<cur1.size();j++) {
| ~^~~~~~~~~~~~
bridges.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for(int k=0;k<cur2.size();k++) {
| ~^~~~~~~~~~~~
bridges.cpp:139:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int k=0;k<cur2.size();k++) {
| ~^~~~~~~~~~~~
bridges.cpp:157:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for(int k=0;k<cur2.size();k++) {
| ~^~~~~~~~~~~~
bridges.cpp:175:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for(int j=0;j<cur2.size();j++) {
| ~^~~~~~~~~~~~
bridges.cpp:192:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for(int j=0,k=0; j< tmp.size() || k< ups.size(); ) {
| ~^~~~~~~~~~~~
bridges.cpp:192:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for(int j=0,k=0; j< tmp.size() || k< ups.size(); ) {
| ~^~~~~~~~~~~~
bridges.cpp:193:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
193 | if(j==tmp.size()) v.push_back(ups[k++]);
| ~^~~~~~~~~~~~
bridges.cpp:194:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | else if(k==ups.size()) v.push_back(tmp[j++]);
| ~^~~~~~~~~~~~
bridges.cpp:199:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for(int j=0;j<cur2.size();j++) dontuse[cur2[j].u]=0;
| ~^~~~~~~~~~~~
bridges.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
52 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
bridges.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
55 | scanf("%d%d%d",&U,&V,&d);
| ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
66 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
bridges.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | scanf("%d%d%d",&t,&u,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3456 KB |
Output is correct |
2 |
Correct |
3 ms |
3456 KB |
Output is correct |
3 |
Correct |
47 ms |
4032 KB |
Output is correct |
4 |
Correct |
28 ms |
4028 KB |
Output is correct |
5 |
Correct |
49 ms |
4020 KB |
Output is correct |
6 |
Correct |
46 ms |
4008 KB |
Output is correct |
7 |
Correct |
46 ms |
3900 KB |
Output is correct |
8 |
Correct |
45 ms |
4028 KB |
Output is correct |
9 |
Correct |
57 ms |
3900 KB |
Output is correct |
10 |
Correct |
44 ms |
4020 KB |
Output is correct |
11 |
Correct |
44 ms |
4028 KB |
Output is correct |
12 |
Correct |
49 ms |
4028 KB |
Output is correct |
13 |
Correct |
49 ms |
4024 KB |
Output is correct |
14 |
Correct |
47 ms |
4032 KB |
Output is correct |
15 |
Correct |
51 ms |
4024 KB |
Output is correct |
16 |
Correct |
53 ms |
3968 KB |
Output is correct |
17 |
Correct |
48 ms |
3900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1396 ms |
10432 KB |
Output is correct |
2 |
Correct |
1302 ms |
10084 KB |
Output is correct |
3 |
Correct |
1331 ms |
10064 KB |
Output is correct |
4 |
Correct |
1281 ms |
10080 KB |
Output is correct |
5 |
Correct |
1312 ms |
10212 KB |
Output is correct |
6 |
Correct |
1719 ms |
9316 KB |
Output is correct |
7 |
Correct |
1693 ms |
9316 KB |
Output is correct |
8 |
Correct |
1611 ms |
9392 KB |
Output is correct |
9 |
Correct |
263 ms |
7328 KB |
Output is correct |
10 |
Correct |
1434 ms |
10032 KB |
Output is correct |
11 |
Correct |
1312 ms |
10252 KB |
Output is correct |
12 |
Correct |
1135 ms |
9440 KB |
Output is correct |
13 |
Correct |
1054 ms |
9064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1145 ms |
9108 KB |
Output is correct |
2 |
Correct |
878 ms |
7616 KB |
Output is correct |
3 |
Correct |
1254 ms |
9192 KB |
Output is correct |
4 |
Correct |
1093 ms |
9192 KB |
Output is correct |
5 |
Correct |
263 ms |
7268 KB |
Output is correct |
6 |
Correct |
1189 ms |
9184 KB |
Output is correct |
7 |
Correct |
1047 ms |
9064 KB |
Output is correct |
8 |
Correct |
978 ms |
9012 KB |
Output is correct |
9 |
Correct |
901 ms |
8868 KB |
Output is correct |
10 |
Correct |
842 ms |
8884 KB |
Output is correct |
11 |
Correct |
812 ms |
8884 KB |
Output is correct |
12 |
Correct |
679 ms |
9192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2241 ms |
10556 KB |
Output is correct |
2 |
Correct |
307 ms |
7400 KB |
Output is correct |
3 |
Correct |
196 ms |
7536 KB |
Output is correct |
4 |
Correct |
119 ms |
7532 KB |
Output is correct |
5 |
Correct |
1427 ms |
10784 KB |
Output is correct |
6 |
Correct |
1937 ms |
10636 KB |
Output is correct |
7 |
Correct |
1882 ms |
10868 KB |
Output is correct |
8 |
Correct |
941 ms |
9276 KB |
Output is correct |
9 |
Correct |
932 ms |
9316 KB |
Output is correct |
10 |
Correct |
957 ms |
9460 KB |
Output is correct |
11 |
Correct |
1476 ms |
10076 KB |
Output is correct |
12 |
Correct |
1405 ms |
10256 KB |
Output is correct |
13 |
Correct |
1459 ms |
10276 KB |
Output is correct |
14 |
Correct |
1174 ms |
11044 KB |
Output is correct |
15 |
Correct |
1203 ms |
10800 KB |
Output is correct |
16 |
Correct |
1718 ms |
10840 KB |
Output is correct |
17 |
Correct |
1789 ms |
10764 KB |
Output is correct |
18 |
Correct |
1794 ms |
10764 KB |
Output is correct |
19 |
Correct |
1715 ms |
11004 KB |
Output is correct |
20 |
Correct |
1639 ms |
10780 KB |
Output is correct |
21 |
Correct |
1615 ms |
10660 KB |
Output is correct |
22 |
Correct |
1640 ms |
11036 KB |
Output is correct |
23 |
Correct |
1494 ms |
10660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1396 ms |
10432 KB |
Output is correct |
2 |
Correct |
1302 ms |
10084 KB |
Output is correct |
3 |
Correct |
1331 ms |
10064 KB |
Output is correct |
4 |
Correct |
1281 ms |
10080 KB |
Output is correct |
5 |
Correct |
1312 ms |
10212 KB |
Output is correct |
6 |
Correct |
1719 ms |
9316 KB |
Output is correct |
7 |
Correct |
1693 ms |
9316 KB |
Output is correct |
8 |
Correct |
1611 ms |
9392 KB |
Output is correct |
9 |
Correct |
263 ms |
7328 KB |
Output is correct |
10 |
Correct |
1434 ms |
10032 KB |
Output is correct |
11 |
Correct |
1312 ms |
10252 KB |
Output is correct |
12 |
Correct |
1135 ms |
9440 KB |
Output is correct |
13 |
Correct |
1054 ms |
9064 KB |
Output is correct |
14 |
Correct |
1145 ms |
9108 KB |
Output is correct |
15 |
Correct |
878 ms |
7616 KB |
Output is correct |
16 |
Correct |
1254 ms |
9192 KB |
Output is correct |
17 |
Correct |
1093 ms |
9192 KB |
Output is correct |
18 |
Correct |
263 ms |
7268 KB |
Output is correct |
19 |
Correct |
1189 ms |
9184 KB |
Output is correct |
20 |
Correct |
1047 ms |
9064 KB |
Output is correct |
21 |
Correct |
978 ms |
9012 KB |
Output is correct |
22 |
Correct |
901 ms |
8868 KB |
Output is correct |
23 |
Correct |
842 ms |
8884 KB |
Output is correct |
24 |
Correct |
812 ms |
8884 KB |
Output is correct |
25 |
Correct |
679 ms |
9192 KB |
Output is correct |
26 |
Correct |
1491 ms |
10340 KB |
Output is correct |
27 |
Correct |
1656 ms |
10316 KB |
Output is correct |
28 |
Correct |
1418 ms |
10480 KB |
Output is correct |
29 |
Correct |
1188 ms |
10336 KB |
Output is correct |
30 |
Correct |
1634 ms |
10332 KB |
Output is correct |
31 |
Correct |
1709 ms |
10444 KB |
Output is correct |
32 |
Correct |
1848 ms |
10432 KB |
Output is correct |
33 |
Correct |
1483 ms |
10308 KB |
Output is correct |
34 |
Correct |
1793 ms |
10408 KB |
Output is correct |
35 |
Correct |
1558 ms |
10656 KB |
Output is correct |
36 |
Correct |
1309 ms |
10608 KB |
Output is correct |
37 |
Correct |
1189 ms |
10492 KB |
Output is correct |
38 |
Correct |
1176 ms |
10604 KB |
Output is correct |
39 |
Correct |
1093 ms |
10124 KB |
Output is correct |
40 |
Correct |
1150 ms |
10308 KB |
Output is correct |
41 |
Correct |
1099 ms |
10696 KB |
Output is correct |
42 |
Correct |
930 ms |
10972 KB |
Output is correct |
43 |
Correct |
935 ms |
10988 KB |
Output is correct |
44 |
Correct |
875 ms |
11032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3456 KB |
Output is correct |
2 |
Correct |
3 ms |
3456 KB |
Output is correct |
3 |
Correct |
47 ms |
4032 KB |
Output is correct |
4 |
Correct |
28 ms |
4028 KB |
Output is correct |
5 |
Correct |
49 ms |
4020 KB |
Output is correct |
6 |
Correct |
46 ms |
4008 KB |
Output is correct |
7 |
Correct |
46 ms |
3900 KB |
Output is correct |
8 |
Correct |
45 ms |
4028 KB |
Output is correct |
9 |
Correct |
57 ms |
3900 KB |
Output is correct |
10 |
Correct |
44 ms |
4020 KB |
Output is correct |
11 |
Correct |
44 ms |
4028 KB |
Output is correct |
12 |
Correct |
49 ms |
4028 KB |
Output is correct |
13 |
Correct |
49 ms |
4024 KB |
Output is correct |
14 |
Correct |
47 ms |
4032 KB |
Output is correct |
15 |
Correct |
51 ms |
4024 KB |
Output is correct |
16 |
Correct |
53 ms |
3968 KB |
Output is correct |
17 |
Correct |
48 ms |
3900 KB |
Output is correct |
18 |
Correct |
1396 ms |
10432 KB |
Output is correct |
19 |
Correct |
1302 ms |
10084 KB |
Output is correct |
20 |
Correct |
1331 ms |
10064 KB |
Output is correct |
21 |
Correct |
1281 ms |
10080 KB |
Output is correct |
22 |
Correct |
1312 ms |
10212 KB |
Output is correct |
23 |
Correct |
1719 ms |
9316 KB |
Output is correct |
24 |
Correct |
1693 ms |
9316 KB |
Output is correct |
25 |
Correct |
1611 ms |
9392 KB |
Output is correct |
26 |
Correct |
263 ms |
7328 KB |
Output is correct |
27 |
Correct |
1434 ms |
10032 KB |
Output is correct |
28 |
Correct |
1312 ms |
10252 KB |
Output is correct |
29 |
Correct |
1135 ms |
9440 KB |
Output is correct |
30 |
Correct |
1054 ms |
9064 KB |
Output is correct |
31 |
Correct |
1145 ms |
9108 KB |
Output is correct |
32 |
Correct |
878 ms |
7616 KB |
Output is correct |
33 |
Correct |
1254 ms |
9192 KB |
Output is correct |
34 |
Correct |
1093 ms |
9192 KB |
Output is correct |
35 |
Correct |
263 ms |
7268 KB |
Output is correct |
36 |
Correct |
1189 ms |
9184 KB |
Output is correct |
37 |
Correct |
1047 ms |
9064 KB |
Output is correct |
38 |
Correct |
978 ms |
9012 KB |
Output is correct |
39 |
Correct |
901 ms |
8868 KB |
Output is correct |
40 |
Correct |
842 ms |
8884 KB |
Output is correct |
41 |
Correct |
812 ms |
8884 KB |
Output is correct |
42 |
Correct |
679 ms |
9192 KB |
Output is correct |
43 |
Correct |
2241 ms |
10556 KB |
Output is correct |
44 |
Correct |
307 ms |
7400 KB |
Output is correct |
45 |
Correct |
196 ms |
7536 KB |
Output is correct |
46 |
Correct |
119 ms |
7532 KB |
Output is correct |
47 |
Correct |
1427 ms |
10784 KB |
Output is correct |
48 |
Correct |
1937 ms |
10636 KB |
Output is correct |
49 |
Correct |
1882 ms |
10868 KB |
Output is correct |
50 |
Correct |
941 ms |
9276 KB |
Output is correct |
51 |
Correct |
932 ms |
9316 KB |
Output is correct |
52 |
Correct |
957 ms |
9460 KB |
Output is correct |
53 |
Correct |
1476 ms |
10076 KB |
Output is correct |
54 |
Correct |
1405 ms |
10256 KB |
Output is correct |
55 |
Correct |
1459 ms |
10276 KB |
Output is correct |
56 |
Correct |
1174 ms |
11044 KB |
Output is correct |
57 |
Correct |
1203 ms |
10800 KB |
Output is correct |
58 |
Correct |
1718 ms |
10840 KB |
Output is correct |
59 |
Correct |
1789 ms |
10764 KB |
Output is correct |
60 |
Correct |
1794 ms |
10764 KB |
Output is correct |
61 |
Correct |
1715 ms |
11004 KB |
Output is correct |
62 |
Correct |
1639 ms |
10780 KB |
Output is correct |
63 |
Correct |
1615 ms |
10660 KB |
Output is correct |
64 |
Correct |
1640 ms |
11036 KB |
Output is correct |
65 |
Correct |
1494 ms |
10660 KB |
Output is correct |
66 |
Correct |
1491 ms |
10340 KB |
Output is correct |
67 |
Correct |
1656 ms |
10316 KB |
Output is correct |
68 |
Correct |
1418 ms |
10480 KB |
Output is correct |
69 |
Correct |
1188 ms |
10336 KB |
Output is correct |
70 |
Correct |
1634 ms |
10332 KB |
Output is correct |
71 |
Correct |
1709 ms |
10444 KB |
Output is correct |
72 |
Correct |
1848 ms |
10432 KB |
Output is correct |
73 |
Correct |
1483 ms |
10308 KB |
Output is correct |
74 |
Correct |
1793 ms |
10408 KB |
Output is correct |
75 |
Correct |
1558 ms |
10656 KB |
Output is correct |
76 |
Correct |
1309 ms |
10608 KB |
Output is correct |
77 |
Correct |
1189 ms |
10492 KB |
Output is correct |
78 |
Correct |
1176 ms |
10604 KB |
Output is correct |
79 |
Correct |
1093 ms |
10124 KB |
Output is correct |
80 |
Correct |
1150 ms |
10308 KB |
Output is correct |
81 |
Correct |
1099 ms |
10696 KB |
Output is correct |
82 |
Correct |
930 ms |
10972 KB |
Output is correct |
83 |
Correct |
935 ms |
10988 KB |
Output is correct |
84 |
Correct |
875 ms |
11032 KB |
Output is correct |
85 |
Correct |
2125 ms |
12128 KB |
Output is correct |
86 |
Correct |
200 ms |
8096 KB |
Output is correct |
87 |
Correct |
163 ms |
8332 KB |
Output is correct |
88 |
Correct |
1758 ms |
12324 KB |
Output is correct |
89 |
Correct |
1931 ms |
13924 KB |
Output is correct |
90 |
Correct |
1765 ms |
12324 KB |
Output is correct |
91 |
Correct |
1426 ms |
11872 KB |
Output is correct |
92 |
Correct |
1433 ms |
11804 KB |
Output is correct |
93 |
Correct |
1711 ms |
10848 KB |
Output is correct |
94 |
Correct |
2160 ms |
13100 KB |
Output is correct |
95 |
Correct |
2015 ms |
13292 KB |
Output is correct |
96 |
Correct |
2037 ms |
12092 KB |
Output is correct |
97 |
Correct |
1525 ms |
11932 KB |
Output is correct |
98 |
Correct |
1550 ms |
11860 KB |
Output is correct |
99 |
Correct |
2352 ms |
13824 KB |
Output is correct |
100 |
Correct |
2319 ms |
13860 KB |
Output is correct |
101 |
Correct |
2177 ms |
14040 KB |
Output is correct |
102 |
Correct |
2167 ms |
14132 KB |
Output is correct |
103 |
Correct |
2208 ms |
12324 KB |
Output is correct |
104 |
Correct |
2312 ms |
12172 KB |
Output is correct |
105 |
Correct |
1835 ms |
12312 KB |
Output is correct |
106 |
Correct |
1648 ms |
12128 KB |
Output is correct |
107 |
Correct |
2096 ms |
12256 KB |
Output is correct |
108 |
Correct |
2496 ms |
12888 KB |
Output is correct |
109 |
Correct |
2327 ms |
10828 KB |
Output is correct |