#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll mod = 1e9 + 7;
const ll B = 1000;
struct Edge{
ll u,v,w;
};
Edge a[N];
struct Query{
ll type,x,y;
};
Query q[N];
ll n,m,ans[N],lab[N],Q,prv[N];
vector<ll> change,unchange;
bool Is_change[N];
stack<LL> st;
bool lf(ll x,ll y){
return a[x].w > a[y].w;
}
ll Find(ll u){
if (lab[u] < 0) return u;
return Find(lab[u]);
}
void Union(ll P,ll Q){
ll r = Find(P),s = Find(Q);
if (r == s) return;
if (lab[r] > lab[s]) swap(r,s);
st.push({r,lab[r]}); st.push({s,lab[s]});
lab[r] += lab[s]; lab[s] = r;
}
void rollback(ll now){
while(st.size() > now){
lab[st.top().fs] = st.top().sc;
st.pop();
}
}
vector<ll> type2;
bool cmp(ll a,ll b){
return q[a].y > q[b].y;
}
bool cmp1(ll a,ll b){
return q[a].y < q[b].y;
}
void oper(ll L,ll R){
memset(Is_change,0,sizeof(Is_change)); memset(lab,-1,sizeof(lab));
change.clear(); unchange.clear(); type2.clear();
vector<ll> to_join[1003];
while(st.size()) st.pop();
for (ll i = L;i <= R;i++){
if (q[i].type == 1) Is_change[q[i].x] = 1,change.emplace_back(i);
else type2.emplace_back(i);
}
for (ll i = 1;i <= m;i++) if (!Is_change[i]) unchange.emplace_back(i);
for (ll i = L;i <= R;i++){
if (q[i].type == 1) a[q[i].x].w = q[i].y;
else{
to_join[i - L].clear();
for (auto j : change) if (a[q[j].x].w >= q[i].y) to_join[i - L].emplace_back(q[j].x);
}
}
sort(unchange.begin(),unchange.end(),lf); sort(type2.begin(),type2.end(),cmp);
ll cur = 0;
for (auto i : type2){
while(cur < unchange.size() && a[unchange[cur]].w >= q[i].y){
Edge p = a[unchange[cur]]; Union(p.u,p.v);
cur++;
}
ll prv = st.size();
for (auto j : to_join[i - L]) Union(a[j].u,a[j].v);
ans[i] = -lab[Find(q[i].x)];
rollback(prv);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n>>m;
for (ll i = 1;i <= m;i++) cin>>a[i].u>>a[i].v>>a[i].w;
cin>>Q;
for (ll i = 1;i <= Q;i++) cin>>q[i].type>>q[i].x>>q[i].y;
for (ll i = 1;i <= Q;i += B) oper(i,min(Q,i + B - 1));
for (ll i = 1;i <= Q;i++) if (ans[i]) cout<<ans[i]<<"\n";
}
Compilation message
bridges.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
bridges.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:46:21: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | while(st.size() > now){
| ~~~~~~~~~~^~~~~
bridges.cpp: In function 'void oper(int, int)':
bridges.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | while(cur < unchange.size() && a[unchange[cur]].w >= q[i].y){
| ~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
97 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
876 KB |
Output is correct |
2 |
Correct |
1 ms |
876 KB |
Output is correct |
3 |
Correct |
48 ms |
1900 KB |
Output is correct |
4 |
Correct |
5 ms |
1004 KB |
Output is correct |
5 |
Correct |
46 ms |
2028 KB |
Output is correct |
6 |
Correct |
36 ms |
2060 KB |
Output is correct |
7 |
Correct |
45 ms |
2288 KB |
Output is correct |
8 |
Correct |
47 ms |
1900 KB |
Output is correct |
9 |
Correct |
67 ms |
3032 KB |
Output is correct |
10 |
Correct |
50 ms |
1772 KB |
Output is correct |
11 |
Correct |
50 ms |
1900 KB |
Output is correct |
12 |
Correct |
60 ms |
2028 KB |
Output is correct |
13 |
Correct |
59 ms |
1920 KB |
Output is correct |
14 |
Correct |
53 ms |
1808 KB |
Output is correct |
15 |
Correct |
66 ms |
1900 KB |
Output is correct |
16 |
Correct |
63 ms |
2444 KB |
Output is correct |
17 |
Correct |
54 ms |
2264 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1933 ms |
4920 KB |
Output is correct |
2 |
Correct |
1959 ms |
5032 KB |
Output is correct |
3 |
Correct |
1985 ms |
4868 KB |
Output is correct |
4 |
Correct |
2056 ms |
4828 KB |
Output is correct |
5 |
Correct |
1994 ms |
4864 KB |
Output is correct |
6 |
Correct |
2886 ms |
6380 KB |
Output is correct |
7 |
Correct |
2950 ms |
6080 KB |
Output is correct |
8 |
Correct |
2851 ms |
6128 KB |
Output is correct |
9 |
Correct |
45 ms |
2668 KB |
Output is correct |
10 |
Correct |
1695 ms |
5532 KB |
Output is correct |
11 |
Correct |
1579 ms |
5388 KB |
Output is correct |
12 |
Correct |
1727 ms |
5144 KB |
Output is correct |
13 |
Correct |
1694 ms |
4640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1544 ms |
4436 KB |
Output is correct |
2 |
Correct |
1241 ms |
4368 KB |
Output is correct |
3 |
Correct |
1854 ms |
5140 KB |
Output is correct |
4 |
Correct |
1557 ms |
4844 KB |
Output is correct |
5 |
Correct |
45 ms |
2572 KB |
Output is correct |
6 |
Correct |
1720 ms |
4612 KB |
Output is correct |
7 |
Correct |
1419 ms |
4552 KB |
Output is correct |
8 |
Correct |
1215 ms |
4204 KB |
Output is correct |
9 |
Correct |
1054 ms |
4320 KB |
Output is correct |
10 |
Correct |
931 ms |
4204 KB |
Output is correct |
11 |
Correct |
1028 ms |
3948 KB |
Output is correct |
12 |
Correct |
906 ms |
3820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2259 ms |
5500 KB |
Output is correct |
2 |
Correct |
45 ms |
2668 KB |
Output is correct |
3 |
Correct |
229 ms |
2984 KB |
Output is correct |
4 |
Correct |
108 ms |
2800 KB |
Output is correct |
5 |
Correct |
1180 ms |
5612 KB |
Output is correct |
6 |
Correct |
2247 ms |
5372 KB |
Output is correct |
7 |
Correct |
1158 ms |
5452 KB |
Output is correct |
8 |
Correct |
1095 ms |
4296 KB |
Output is correct |
9 |
Correct |
1083 ms |
4348 KB |
Output is correct |
10 |
Correct |
1102 ms |
4428 KB |
Output is correct |
11 |
Correct |
1677 ms |
4848 KB |
Output is correct |
12 |
Correct |
1658 ms |
4748 KB |
Output is correct |
13 |
Correct |
1667 ms |
5100 KB |
Output is correct |
14 |
Correct |
1054 ms |
5436 KB |
Output is correct |
15 |
Correct |
1110 ms |
5356 KB |
Output is correct |
16 |
Correct |
2234 ms |
5228 KB |
Output is correct |
17 |
Correct |
2236 ms |
5388 KB |
Output is correct |
18 |
Correct |
2256 ms |
5228 KB |
Output is correct |
19 |
Correct |
2236 ms |
5228 KB |
Output is correct |
20 |
Correct |
1877 ms |
5420 KB |
Output is correct |
21 |
Correct |
1878 ms |
5228 KB |
Output is correct |
22 |
Correct |
2128 ms |
5484 KB |
Output is correct |
23 |
Correct |
1266 ms |
5100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1933 ms |
4920 KB |
Output is correct |
2 |
Correct |
1959 ms |
5032 KB |
Output is correct |
3 |
Correct |
1985 ms |
4868 KB |
Output is correct |
4 |
Correct |
2056 ms |
4828 KB |
Output is correct |
5 |
Correct |
1994 ms |
4864 KB |
Output is correct |
6 |
Correct |
2886 ms |
6380 KB |
Output is correct |
7 |
Correct |
2950 ms |
6080 KB |
Output is correct |
8 |
Correct |
2851 ms |
6128 KB |
Output is correct |
9 |
Correct |
45 ms |
2668 KB |
Output is correct |
10 |
Correct |
1695 ms |
5532 KB |
Output is correct |
11 |
Correct |
1579 ms |
5388 KB |
Output is correct |
12 |
Correct |
1727 ms |
5144 KB |
Output is correct |
13 |
Correct |
1694 ms |
4640 KB |
Output is correct |
14 |
Correct |
1544 ms |
4436 KB |
Output is correct |
15 |
Correct |
1241 ms |
4368 KB |
Output is correct |
16 |
Correct |
1854 ms |
5140 KB |
Output is correct |
17 |
Correct |
1557 ms |
4844 KB |
Output is correct |
18 |
Correct |
45 ms |
2572 KB |
Output is correct |
19 |
Correct |
1720 ms |
4612 KB |
Output is correct |
20 |
Correct |
1419 ms |
4552 KB |
Output is correct |
21 |
Correct |
1215 ms |
4204 KB |
Output is correct |
22 |
Correct |
1054 ms |
4320 KB |
Output is correct |
23 |
Correct |
931 ms |
4204 KB |
Output is correct |
24 |
Correct |
1028 ms |
3948 KB |
Output is correct |
25 |
Correct |
906 ms |
3820 KB |
Output is correct |
26 |
Correct |
1937 ms |
5000 KB |
Output is correct |
27 |
Correct |
2397 ms |
5780 KB |
Output is correct |
28 |
Correct |
2013 ms |
5264 KB |
Output is correct |
29 |
Correct |
1435 ms |
4616 KB |
Output is correct |
30 |
Correct |
2261 ms |
5444 KB |
Output is correct |
31 |
Correct |
2396 ms |
5788 KB |
Output is correct |
32 |
Correct |
2314 ms |
5236 KB |
Output is correct |
33 |
Correct |
1966 ms |
4904 KB |
Output is correct |
34 |
Correct |
1976 ms |
5160 KB |
Output is correct |
35 |
Correct |
1977 ms |
5028 KB |
Output is correct |
36 |
Correct |
1515 ms |
4492 KB |
Output is correct |
37 |
Correct |
1504 ms |
4584 KB |
Output is correct |
38 |
Correct |
1475 ms |
4732 KB |
Output is correct |
39 |
Correct |
1261 ms |
4404 KB |
Output is correct |
40 |
Correct |
1256 ms |
4392 KB |
Output is correct |
41 |
Correct |
1250 ms |
4576 KB |
Output is correct |
42 |
Correct |
1214 ms |
4324 KB |
Output is correct |
43 |
Correct |
1213 ms |
4236 KB |
Output is correct |
44 |
Correct |
1203 ms |
4368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
876 KB |
Output is correct |
2 |
Correct |
1 ms |
876 KB |
Output is correct |
3 |
Correct |
48 ms |
1900 KB |
Output is correct |
4 |
Correct |
5 ms |
1004 KB |
Output is correct |
5 |
Correct |
46 ms |
2028 KB |
Output is correct |
6 |
Correct |
36 ms |
2060 KB |
Output is correct |
7 |
Correct |
45 ms |
2288 KB |
Output is correct |
8 |
Correct |
47 ms |
1900 KB |
Output is correct |
9 |
Correct |
67 ms |
3032 KB |
Output is correct |
10 |
Correct |
50 ms |
1772 KB |
Output is correct |
11 |
Correct |
50 ms |
1900 KB |
Output is correct |
12 |
Correct |
60 ms |
2028 KB |
Output is correct |
13 |
Correct |
59 ms |
1920 KB |
Output is correct |
14 |
Correct |
53 ms |
1808 KB |
Output is correct |
15 |
Correct |
66 ms |
1900 KB |
Output is correct |
16 |
Correct |
63 ms |
2444 KB |
Output is correct |
17 |
Correct |
54 ms |
2264 KB |
Output is correct |
18 |
Correct |
1933 ms |
4920 KB |
Output is correct |
19 |
Correct |
1959 ms |
5032 KB |
Output is correct |
20 |
Correct |
1985 ms |
4868 KB |
Output is correct |
21 |
Correct |
2056 ms |
4828 KB |
Output is correct |
22 |
Correct |
1994 ms |
4864 KB |
Output is correct |
23 |
Correct |
2886 ms |
6380 KB |
Output is correct |
24 |
Correct |
2950 ms |
6080 KB |
Output is correct |
25 |
Correct |
2851 ms |
6128 KB |
Output is correct |
26 |
Correct |
45 ms |
2668 KB |
Output is correct |
27 |
Correct |
1695 ms |
5532 KB |
Output is correct |
28 |
Correct |
1579 ms |
5388 KB |
Output is correct |
29 |
Correct |
1727 ms |
5144 KB |
Output is correct |
30 |
Correct |
1694 ms |
4640 KB |
Output is correct |
31 |
Correct |
1544 ms |
4436 KB |
Output is correct |
32 |
Correct |
1241 ms |
4368 KB |
Output is correct |
33 |
Correct |
1854 ms |
5140 KB |
Output is correct |
34 |
Correct |
1557 ms |
4844 KB |
Output is correct |
35 |
Correct |
45 ms |
2572 KB |
Output is correct |
36 |
Correct |
1720 ms |
4612 KB |
Output is correct |
37 |
Correct |
1419 ms |
4552 KB |
Output is correct |
38 |
Correct |
1215 ms |
4204 KB |
Output is correct |
39 |
Correct |
1054 ms |
4320 KB |
Output is correct |
40 |
Correct |
931 ms |
4204 KB |
Output is correct |
41 |
Correct |
1028 ms |
3948 KB |
Output is correct |
42 |
Correct |
906 ms |
3820 KB |
Output is correct |
43 |
Correct |
2259 ms |
5500 KB |
Output is correct |
44 |
Correct |
45 ms |
2668 KB |
Output is correct |
45 |
Correct |
229 ms |
2984 KB |
Output is correct |
46 |
Correct |
108 ms |
2800 KB |
Output is correct |
47 |
Correct |
1180 ms |
5612 KB |
Output is correct |
48 |
Correct |
2247 ms |
5372 KB |
Output is correct |
49 |
Correct |
1158 ms |
5452 KB |
Output is correct |
50 |
Correct |
1095 ms |
4296 KB |
Output is correct |
51 |
Correct |
1083 ms |
4348 KB |
Output is correct |
52 |
Correct |
1102 ms |
4428 KB |
Output is correct |
53 |
Correct |
1677 ms |
4848 KB |
Output is correct |
54 |
Correct |
1658 ms |
4748 KB |
Output is correct |
55 |
Correct |
1667 ms |
5100 KB |
Output is correct |
56 |
Correct |
1054 ms |
5436 KB |
Output is correct |
57 |
Correct |
1110 ms |
5356 KB |
Output is correct |
58 |
Correct |
2234 ms |
5228 KB |
Output is correct |
59 |
Correct |
2236 ms |
5388 KB |
Output is correct |
60 |
Correct |
2256 ms |
5228 KB |
Output is correct |
61 |
Correct |
2236 ms |
5228 KB |
Output is correct |
62 |
Correct |
1877 ms |
5420 KB |
Output is correct |
63 |
Correct |
1878 ms |
5228 KB |
Output is correct |
64 |
Correct |
2128 ms |
5484 KB |
Output is correct |
65 |
Correct |
1266 ms |
5100 KB |
Output is correct |
66 |
Correct |
1937 ms |
5000 KB |
Output is correct |
67 |
Correct |
2397 ms |
5780 KB |
Output is correct |
68 |
Correct |
2013 ms |
5264 KB |
Output is correct |
69 |
Correct |
1435 ms |
4616 KB |
Output is correct |
70 |
Correct |
2261 ms |
5444 KB |
Output is correct |
71 |
Correct |
2396 ms |
5788 KB |
Output is correct |
72 |
Correct |
2314 ms |
5236 KB |
Output is correct |
73 |
Correct |
1966 ms |
4904 KB |
Output is correct |
74 |
Correct |
1976 ms |
5160 KB |
Output is correct |
75 |
Correct |
1977 ms |
5028 KB |
Output is correct |
76 |
Correct |
1515 ms |
4492 KB |
Output is correct |
77 |
Correct |
1504 ms |
4584 KB |
Output is correct |
78 |
Correct |
1475 ms |
4732 KB |
Output is correct |
79 |
Correct |
1261 ms |
4404 KB |
Output is correct |
80 |
Correct |
1256 ms |
4392 KB |
Output is correct |
81 |
Correct |
1250 ms |
4576 KB |
Output is correct |
82 |
Correct |
1214 ms |
4324 KB |
Output is correct |
83 |
Correct |
1213 ms |
4236 KB |
Output is correct |
84 |
Correct |
1203 ms |
4368 KB |
Output is correct |
85 |
Correct |
2854 ms |
6152 KB |
Output is correct |
86 |
Correct |
269 ms |
3292 KB |
Output is correct |
87 |
Correct |
162 ms |
4456 KB |
Output is correct |
88 |
Correct |
1770 ms |
6388 KB |
Output is correct |
89 |
Correct |
2875 ms |
5972 KB |
Output is correct |
90 |
Correct |
1796 ms |
6680 KB |
Output is correct |
91 |
Correct |
2025 ms |
4980 KB |
Output is correct |
92 |
Correct |
2003 ms |
5232 KB |
Output is correct |
93 |
Correct |
2861 ms |
5820 KB |
Output is correct |
94 |
Correct |
2391 ms |
5368 KB |
Output is correct |
95 |
Correct |
2401 ms |
5304 KB |
Output is correct |
96 |
Correct |
2734 ms |
6308 KB |
Output is correct |
97 |
Correct |
1436 ms |
5868 KB |
Output is correct |
98 |
Correct |
1441 ms |
5304 KB |
Output is correct |
99 |
Correct |
2875 ms |
5780 KB |
Output is correct |
100 |
Correct |
2848 ms |
5808 KB |
Output is correct |
101 |
Correct |
2940 ms |
6152 KB |
Output is correct |
102 |
Correct |
2931 ms |
5724 KB |
Output is correct |
103 |
Correct |
2979 ms |
6832 KB |
Output is correct |
104 |
Correct |
2978 ms |
10028 KB |
Output is correct |
105 |
Correct |
2293 ms |
8760 KB |
Output is correct |
106 |
Correct |
1868 ms |
8228 KB |
Output is correct |
107 |
Correct |
2214 ms |
8968 KB |
Output is correct |
108 |
Correct |
2918 ms |
9732 KB |
Output is correct |
109 |
Correct |
2063 ms |
8224 KB |
Output is correct |