#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using namespace std;
using lli = long long;
using pii = pair<int,int>;
struct edge{
int u,v,w,i,c;
int l,r;
bool operator<(const edge &rhs)const {
return w<rhs.w;
}
}arr[200000];
struct qd{
int t,a,b;
bool operator<(const qd &rhs)const {
return b<rhs.b;
}
}qa[100000];
int n,m,q;
struct dsu{
int pa[50001],sz[50001],tp[50001],ts[50001],tf[50001];
int ti;
void init() {
for(int i=1;i<=n;i++) pa[i]=i, sz[i]=1, tf[i]=-1;
}
int find(int cur) {
return cur==pa[cur] ? cur : pa[cur] = find(pa[cur]);
}
void merge(int u,int v) {
u = find(u); v=find(v);
if(u!=v) {
pa[v]=u; sz[u]+=sz[v];
}
}
void tcheck(int cur) {
if(tf[cur]!=ti) tf[cur]=ti, tp[cur]=pa[cur], ts[cur]=sz[cur];
}
int tfind(int cur) {
tcheck(cur);
return cur==tp[cur] ? cur : tp[cur] = tfind(tp[cur]);
}
void tmerge(int u,int v) {
u=tfind(u), v=tfind(v);
if(u!=v) {
tp[v]=u;
ts[u] += ts[v];
}
}
int tgetsz(int cur) {
cur=tfind(cur);
return ts[cur];
}
}ds;
int ans[100000],pr[100000];
int main() {
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++) {
scanf("%d%d%d",&arr[i].u,&arr[i].v,&arr[i].w);
arr[i].w = -arr[i].w;
arr[i].i = i; arr[i].c = -1;
}
scanf("%d",&q);
for(int i=0;i<m;i++) arr[i].l=-1,arr[i].r=q, pr[i] = i;
for(int i=0;i<q;i++) {
scanf("%d%d%d",&qa[i].t,&qa[i].a,&qa[i].b);
qa[i].b = -qa[i].b;
if(qa[i].t==1) {
qa[i].a--;
int idx = pr[qa[i].a];
arr[m] = arr[idx];
arr[m].w = qa[i].b;
arr[idx].r = i;
arr[m].l = i;
pr[qa[i].a] = m++;
}
}
sort(arr,arr+m);
const int B = 350;
for(int bi=0;bi*B<q;bi++) {
vector<pair<qd,int>> a2;
vector<edge> a1;
for(int i=bi*B;i<min(bi*B+B, q);i++) {
if(qa[i].t==2) a2.push_back({qa[i], i});
}
sort(a2.begin(),a2.end());
int s=bi*B, e=min(bi*B+B,q);
for(int i=0;i<m;i++) {
if((s<=arr[i].l && arr[i].l<e) || (s<=arr[i].r && arr[i].r<e)) arr[i].c=bi,a1.push_back(arr[i]);
}
int ei=0;
ds.init();
for(int i=0;i<sz(a2);i++) {
ds.ti=i;
for(;ei<m && arr[ei].w <= a2[i].fi.b; ei++) if(arr[ei].c!=bi && arr[ei].l<s && arr[ei].r>=e) {
ds.merge(arr[ei].u, arr[ei].v);
}
for(int j=0;j<sz(a1);j++) {
if(a1[j].l<=a2[i].se && a2[i].se<=a1[j].r && a1[j].w <= a2[i].fi.b) ds.tmerge(a1[j].u,a1[j].v);
}
ans[a2[i].se] = ds.tgetsz(a2[i].fi.a);
}
}
for(int i=0;i<q;i++) if(qa[i].t==2) printf("%d\n",ans[i]);
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
bridges.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&arr[i].u,&arr[i].v,&arr[i].w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
bridges.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&qa[i].t,&qa[i].a,&qa[i].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
27 ms |
760 KB |
Output is correct |
4 |
Correct |
7 ms |
504 KB |
Output is correct |
5 |
Correct |
20 ms |
760 KB |
Output is correct |
6 |
Correct |
16 ms |
760 KB |
Output is correct |
7 |
Correct |
19 ms |
636 KB |
Output is correct |
8 |
Correct |
22 ms |
732 KB |
Output is correct |
9 |
Correct |
19 ms |
632 KB |
Output is correct |
10 |
Correct |
22 ms |
760 KB |
Output is correct |
11 |
Correct |
22 ms |
760 KB |
Output is correct |
12 |
Correct |
22 ms |
632 KB |
Output is correct |
13 |
Correct |
26 ms |
748 KB |
Output is correct |
14 |
Correct |
25 ms |
808 KB |
Output is correct |
15 |
Correct |
25 ms |
760 KB |
Output is correct |
16 |
Correct |
18 ms |
760 KB |
Output is correct |
17 |
Correct |
19 ms |
760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1238 ms |
6168 KB |
Output is correct |
2 |
Correct |
1248 ms |
8768 KB |
Output is correct |
3 |
Correct |
1234 ms |
8824 KB |
Output is correct |
4 |
Correct |
1430 ms |
8812 KB |
Output is correct |
5 |
Correct |
1404 ms |
8864 KB |
Output is correct |
6 |
Correct |
1858 ms |
8800 KB |
Output is correct |
7 |
Correct |
1898 ms |
8732 KB |
Output is correct |
8 |
Correct |
1832 ms |
8896 KB |
Output is correct |
9 |
Correct |
48 ms |
3448 KB |
Output is correct |
10 |
Correct |
1231 ms |
7812 KB |
Output is correct |
11 |
Correct |
1315 ms |
7636 KB |
Output is correct |
12 |
Correct |
912 ms |
7808 KB |
Output is correct |
13 |
Correct |
1514 ms |
9732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
971 ms |
5092 KB |
Output is correct |
2 |
Correct |
596 ms |
5436 KB |
Output is correct |
3 |
Correct |
1031 ms |
7404 KB |
Output is correct |
4 |
Correct |
948 ms |
7644 KB |
Output is correct |
5 |
Correct |
48 ms |
3448 KB |
Output is correct |
6 |
Correct |
999 ms |
7476 KB |
Output is correct |
7 |
Correct |
933 ms |
7500 KB |
Output is correct |
8 |
Correct |
881 ms |
7672 KB |
Output is correct |
9 |
Correct |
496 ms |
6484 KB |
Output is correct |
10 |
Correct |
477 ms |
6368 KB |
Output is correct |
11 |
Correct |
990 ms |
8456 KB |
Output is correct |
12 |
Correct |
942 ms |
8572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1814 ms |
6520 KB |
Output is correct |
2 |
Correct |
48 ms |
3448 KB |
Output is correct |
3 |
Correct |
76 ms |
5624 KB |
Output is correct |
4 |
Correct |
67 ms |
5624 KB |
Output is correct |
5 |
Correct |
1817 ms |
8836 KB |
Output is correct |
6 |
Correct |
1816 ms |
9612 KB |
Output is correct |
7 |
Correct |
1789 ms |
8888 KB |
Output is correct |
8 |
Correct |
674 ms |
7416 KB |
Output is correct |
9 |
Correct |
699 ms |
7544 KB |
Output is correct |
10 |
Correct |
699 ms |
7440 KB |
Output is correct |
11 |
Correct |
1133 ms |
8752 KB |
Output is correct |
12 |
Correct |
1067 ms |
8696 KB |
Output is correct |
13 |
Correct |
1134 ms |
8816 KB |
Output is correct |
14 |
Correct |
1781 ms |
8968 KB |
Output is correct |
15 |
Correct |
1837 ms |
8944 KB |
Output is correct |
16 |
Correct |
1727 ms |
9692 KB |
Output is correct |
17 |
Correct |
1718 ms |
9672 KB |
Output is correct |
18 |
Correct |
1627 ms |
9608 KB |
Output is correct |
19 |
Correct |
1621 ms |
9628 KB |
Output is correct |
20 |
Correct |
1234 ms |
9316 KB |
Output is correct |
21 |
Correct |
1222 ms |
9312 KB |
Output is correct |
22 |
Correct |
1659 ms |
9552 KB |
Output is correct |
23 |
Correct |
1312 ms |
8252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1238 ms |
6168 KB |
Output is correct |
2 |
Correct |
1248 ms |
8768 KB |
Output is correct |
3 |
Correct |
1234 ms |
8824 KB |
Output is correct |
4 |
Correct |
1430 ms |
8812 KB |
Output is correct |
5 |
Correct |
1404 ms |
8864 KB |
Output is correct |
6 |
Correct |
1858 ms |
8800 KB |
Output is correct |
7 |
Correct |
1898 ms |
8732 KB |
Output is correct |
8 |
Correct |
1832 ms |
8896 KB |
Output is correct |
9 |
Correct |
48 ms |
3448 KB |
Output is correct |
10 |
Correct |
1231 ms |
7812 KB |
Output is correct |
11 |
Correct |
1315 ms |
7636 KB |
Output is correct |
12 |
Correct |
912 ms |
7808 KB |
Output is correct |
13 |
Correct |
1514 ms |
9732 KB |
Output is correct |
14 |
Correct |
971 ms |
5092 KB |
Output is correct |
15 |
Correct |
596 ms |
5436 KB |
Output is correct |
16 |
Correct |
1031 ms |
7404 KB |
Output is correct |
17 |
Correct |
948 ms |
7644 KB |
Output is correct |
18 |
Correct |
48 ms |
3448 KB |
Output is correct |
19 |
Correct |
999 ms |
7476 KB |
Output is correct |
20 |
Correct |
933 ms |
7500 KB |
Output is correct |
21 |
Correct |
881 ms |
7672 KB |
Output is correct |
22 |
Correct |
496 ms |
6484 KB |
Output is correct |
23 |
Correct |
477 ms |
6368 KB |
Output is correct |
24 |
Correct |
990 ms |
8456 KB |
Output is correct |
25 |
Correct |
942 ms |
8572 KB |
Output is correct |
26 |
Correct |
1250 ms |
8804 KB |
Output is correct |
27 |
Correct |
2424 ms |
8696 KB |
Output is correct |
28 |
Correct |
2165 ms |
8908 KB |
Output is correct |
29 |
Correct |
1621 ms |
8884 KB |
Output is correct |
30 |
Correct |
1959 ms |
8624 KB |
Output is correct |
31 |
Correct |
2051 ms |
8696 KB |
Output is correct |
32 |
Correct |
2094 ms |
8756 KB |
Output is correct |
33 |
Correct |
1659 ms |
8836 KB |
Output is correct |
34 |
Correct |
1643 ms |
8700 KB |
Output is correct |
35 |
Correct |
1751 ms |
9024 KB |
Output is correct |
36 |
Correct |
1383 ms |
8700 KB |
Output is correct |
37 |
Correct |
1403 ms |
8776 KB |
Output is correct |
38 |
Correct |
1441 ms |
8892 KB |
Output is correct |
39 |
Correct |
905 ms |
7708 KB |
Output is correct |
40 |
Correct |
931 ms |
7928 KB |
Output is correct |
41 |
Correct |
939 ms |
7700 KB |
Output is correct |
42 |
Correct |
1418 ms |
9832 KB |
Output is correct |
43 |
Correct |
1526 ms |
9760 KB |
Output is correct |
44 |
Correct |
1408 ms |
9680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
27 ms |
760 KB |
Output is correct |
4 |
Correct |
7 ms |
504 KB |
Output is correct |
5 |
Correct |
20 ms |
760 KB |
Output is correct |
6 |
Correct |
16 ms |
760 KB |
Output is correct |
7 |
Correct |
19 ms |
636 KB |
Output is correct |
8 |
Correct |
22 ms |
732 KB |
Output is correct |
9 |
Correct |
19 ms |
632 KB |
Output is correct |
10 |
Correct |
22 ms |
760 KB |
Output is correct |
11 |
Correct |
22 ms |
760 KB |
Output is correct |
12 |
Correct |
22 ms |
632 KB |
Output is correct |
13 |
Correct |
26 ms |
748 KB |
Output is correct |
14 |
Correct |
25 ms |
808 KB |
Output is correct |
15 |
Correct |
25 ms |
760 KB |
Output is correct |
16 |
Correct |
18 ms |
760 KB |
Output is correct |
17 |
Correct |
19 ms |
760 KB |
Output is correct |
18 |
Correct |
1238 ms |
6168 KB |
Output is correct |
19 |
Correct |
1248 ms |
8768 KB |
Output is correct |
20 |
Correct |
1234 ms |
8824 KB |
Output is correct |
21 |
Correct |
1430 ms |
8812 KB |
Output is correct |
22 |
Correct |
1404 ms |
8864 KB |
Output is correct |
23 |
Correct |
1858 ms |
8800 KB |
Output is correct |
24 |
Correct |
1898 ms |
8732 KB |
Output is correct |
25 |
Correct |
1832 ms |
8896 KB |
Output is correct |
26 |
Correct |
48 ms |
3448 KB |
Output is correct |
27 |
Correct |
1231 ms |
7812 KB |
Output is correct |
28 |
Correct |
1315 ms |
7636 KB |
Output is correct |
29 |
Correct |
912 ms |
7808 KB |
Output is correct |
30 |
Correct |
1514 ms |
9732 KB |
Output is correct |
31 |
Correct |
971 ms |
5092 KB |
Output is correct |
32 |
Correct |
596 ms |
5436 KB |
Output is correct |
33 |
Correct |
1031 ms |
7404 KB |
Output is correct |
34 |
Correct |
948 ms |
7644 KB |
Output is correct |
35 |
Correct |
48 ms |
3448 KB |
Output is correct |
36 |
Correct |
999 ms |
7476 KB |
Output is correct |
37 |
Correct |
933 ms |
7500 KB |
Output is correct |
38 |
Correct |
881 ms |
7672 KB |
Output is correct |
39 |
Correct |
496 ms |
6484 KB |
Output is correct |
40 |
Correct |
477 ms |
6368 KB |
Output is correct |
41 |
Correct |
990 ms |
8456 KB |
Output is correct |
42 |
Correct |
942 ms |
8572 KB |
Output is correct |
43 |
Correct |
1814 ms |
6520 KB |
Output is correct |
44 |
Correct |
48 ms |
3448 KB |
Output is correct |
45 |
Correct |
76 ms |
5624 KB |
Output is correct |
46 |
Correct |
67 ms |
5624 KB |
Output is correct |
47 |
Correct |
1817 ms |
8836 KB |
Output is correct |
48 |
Correct |
1816 ms |
9612 KB |
Output is correct |
49 |
Correct |
1789 ms |
8888 KB |
Output is correct |
50 |
Correct |
674 ms |
7416 KB |
Output is correct |
51 |
Correct |
699 ms |
7544 KB |
Output is correct |
52 |
Correct |
699 ms |
7440 KB |
Output is correct |
53 |
Correct |
1133 ms |
8752 KB |
Output is correct |
54 |
Correct |
1067 ms |
8696 KB |
Output is correct |
55 |
Correct |
1134 ms |
8816 KB |
Output is correct |
56 |
Correct |
1781 ms |
8968 KB |
Output is correct |
57 |
Correct |
1837 ms |
8944 KB |
Output is correct |
58 |
Correct |
1727 ms |
9692 KB |
Output is correct |
59 |
Correct |
1718 ms |
9672 KB |
Output is correct |
60 |
Correct |
1627 ms |
9608 KB |
Output is correct |
61 |
Correct |
1621 ms |
9628 KB |
Output is correct |
62 |
Correct |
1234 ms |
9316 KB |
Output is correct |
63 |
Correct |
1222 ms |
9312 KB |
Output is correct |
64 |
Correct |
1659 ms |
9552 KB |
Output is correct |
65 |
Correct |
1312 ms |
8252 KB |
Output is correct |
66 |
Correct |
1250 ms |
8804 KB |
Output is correct |
67 |
Correct |
2424 ms |
8696 KB |
Output is correct |
68 |
Correct |
2165 ms |
8908 KB |
Output is correct |
69 |
Correct |
1621 ms |
8884 KB |
Output is correct |
70 |
Correct |
1959 ms |
8624 KB |
Output is correct |
71 |
Correct |
2051 ms |
8696 KB |
Output is correct |
72 |
Correct |
2094 ms |
8756 KB |
Output is correct |
73 |
Correct |
1659 ms |
8836 KB |
Output is correct |
74 |
Correct |
1643 ms |
8700 KB |
Output is correct |
75 |
Correct |
1751 ms |
9024 KB |
Output is correct |
76 |
Correct |
1383 ms |
8700 KB |
Output is correct |
77 |
Correct |
1403 ms |
8776 KB |
Output is correct |
78 |
Correct |
1441 ms |
8892 KB |
Output is correct |
79 |
Correct |
905 ms |
7708 KB |
Output is correct |
80 |
Correct |
931 ms |
7928 KB |
Output is correct |
81 |
Correct |
939 ms |
7700 KB |
Output is correct |
82 |
Correct |
1418 ms |
9832 KB |
Output is correct |
83 |
Correct |
1526 ms |
9760 KB |
Output is correct |
84 |
Correct |
1408 ms |
9680 KB |
Output is correct |
85 |
Execution timed out |
3038 ms |
11560 KB |
Time limit exceeded |
86 |
Halted |
0 ms |
0 KB |
- |