#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
//#define int long long
//#define inf (int)1e18
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
const int nsqrt = 1024;
const int mod = 1e9 + 7;
struct event
{
int u,szu,v,szv;
event(int u,int szu,int v,int szv) : u(u),szu(szu),v(v),szv(szv) {};
};
struct DSU
{
vi par,sz;
DSU(int n) : par(n),sz(n) {};
stack<event> st;
void rollback(int x)
{
if(st.empty()) return;
while(st.size() > x)
{
auto top = st.top();
st.pop();
par[top.v] = top.v;
sz[top.v] = top.szv;
par[top.u] = top.u;
sz[top.u] = top.szu;
}
}
void make(int u)
{
par[u] = u;
sz[u] = 1;
}
int find(int u)
{
return u == par[u] ? u : find(par[u]);
}
void Union(int u,int v)
{
u = find(u);
v = find(v);
if(u == v) return ;
if(sz[u] < sz[v]) swap(u,v);
st.push(event(u, sz[u], v, sz[v]));
sz[u] += sz[v];
par[v] = u;
}
}g(100010);
array<int,3> edge[maxn];
array<int,3> qry[maxn];
int n,m,q;
int ans[maxn];
bool ok[maxn];
vii join[maxn];
void solve(int l,int r)
{
fo(i,1,n) g.make(i);
vi changed,query;
vector<array<int,3>> v;
fo(i,1,m) ok[i] = 0;
fo(i,l,r)
{
if(qry[i][0] > 0) ok[qry[i][1]] = 1,changed.pb(qry[i][1]);
else query.pb(i);
}
// for(int it : changed) cout << it << ' ' ;en;
fo(i,1,m) if(!ok[i]) v.pb(edge[i]);
sort(v.begin(),v.end(),[](array<int,3> a,array<int,3> b)
{
return a[2] > b[2] or (a[2] == b[2] and a[0] > b[0]);
});
sort(query.begin(),query.end(),[](int a,int b)
{
return qry[a][2] > qry[b][2];
});
fo(i,l,r)
{
if(qry[i][0] < 0)
{
for(int it : changed) if(edge[it][2] >= qry[i][2]) join[i].pb(edge[it][0],edge[it][1]);
}
else edge[qry[i][1]][2] = qry[i][2];
}
int ptr = 0;
for(int it : query)
{
while(ptr < (int)v.size() and v[ptr][2] >= qry[it][2]) g.Union(v[ptr][0],v[ptr][1]),ptr++;
int timer = g.st.size();
for(auto [u,v] : join[it]) g.Union(u,v);
ans[it] = g.sz[g.find(qry[it][1])];
g.rollback(timer);
}
}
main()
{
#define name "TASK"
if(fopen(name".inp","r"))
{
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
fo(i,1,m) cin >> edge[i][0] >> edge[i][1] >> edge[i][2];
cin >> q;
fo(i,1,q)
{
cin >> qry[i][0] >> qry[i][1] >> qry[i][2];
if(qry[i][0] == 1) qry[i][0] = i;
else qry[i][0] = -i;
}
for(int i = 1 ; i <= q ; i += nsqrt) solve(i,(min(q,i + nsqrt - 1)));
fo(i,1,q) if(qry[i][0] < 0) cout << ans[i] << "\n";
}
Compilation message
bridges.cpp: In member function 'void DSU::rollback(int)':
bridges.cpp:53:25: warning: comparison of integer expressions of different signedness: 'std::stack<event>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
53 | while(st.size() > x)
| ~~~~~~~~~~^~~
bridges.cpp: At global scope:
bridges.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
128 | main()
| ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
30040 KB |
Output is correct |
2 |
Correct |
9 ms |
30044 KB |
Output is correct |
3 |
Correct |
39 ms |
43856 KB |
Output is correct |
4 |
Correct |
11 ms |
28260 KB |
Output is correct |
5 |
Correct |
39 ms |
46416 KB |
Output is correct |
6 |
Correct |
44 ms |
46172 KB |
Output is correct |
7 |
Correct |
36 ms |
47440 KB |
Output is correct |
8 |
Correct |
40 ms |
42456 KB |
Output is correct |
9 |
Correct |
53 ms |
60244 KB |
Output is correct |
10 |
Correct |
41 ms |
44368 KB |
Output is correct |
11 |
Correct |
41 ms |
43728 KB |
Output is correct |
12 |
Correct |
62 ms |
48516 KB |
Output is correct |
13 |
Correct |
45 ms |
45396 KB |
Output is correct |
14 |
Correct |
45 ms |
43344 KB |
Output is correct |
15 |
Correct |
47 ms |
45004 KB |
Output is correct |
16 |
Correct |
51 ms |
52816 KB |
Output is correct |
17 |
Correct |
46 ms |
50000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1067 ms |
255844 KB |
Output is correct |
2 |
Correct |
1088 ms |
254096 KB |
Output is correct |
3 |
Correct |
1055 ms |
254520 KB |
Output is correct |
4 |
Correct |
1073 ms |
253980 KB |
Output is correct |
5 |
Correct |
1062 ms |
254920 KB |
Output is correct |
6 |
Correct |
1273 ms |
421164 KB |
Output is correct |
7 |
Correct |
1276 ms |
401208 KB |
Output is correct |
8 |
Correct |
1278 ms |
410164 KB |
Output is correct |
9 |
Correct |
37 ms |
33584 KB |
Output is correct |
10 |
Correct |
915 ms |
344108 KB |
Output is correct |
11 |
Correct |
914 ms |
316964 KB |
Output is correct |
12 |
Correct |
838 ms |
209384 KB |
Output is correct |
13 |
Correct |
848 ms |
196492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
809 ms |
227360 KB |
Output is correct |
2 |
Correct |
571 ms |
265560 KB |
Output is correct |
3 |
Correct |
894 ms |
303008 KB |
Output is correct |
4 |
Correct |
791 ms |
225564 KB |
Output is correct |
5 |
Correct |
38 ms |
33616 KB |
Output is correct |
6 |
Correct |
862 ms |
264972 KB |
Output is correct |
7 |
Correct |
744 ms |
211936 KB |
Output is correct |
8 |
Correct |
661 ms |
177788 KB |
Output is correct |
9 |
Correct |
562 ms |
158344 KB |
Output is correct |
10 |
Correct |
522 ms |
135452 KB |
Output is correct |
11 |
Correct |
566 ms |
153292 KB |
Output is correct |
12 |
Correct |
511 ms |
131876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1266 ms |
121116 KB |
Output is correct |
2 |
Correct |
36 ms |
33764 KB |
Output is correct |
3 |
Correct |
146 ms |
36804 KB |
Output is correct |
4 |
Correct |
104 ms |
36916 KB |
Output is correct |
5 |
Correct |
1209 ms |
120004 KB |
Output is correct |
6 |
Correct |
1240 ms |
121388 KB |
Output is correct |
7 |
Correct |
1241 ms |
119640 KB |
Output is correct |
8 |
Correct |
629 ms |
117984 KB |
Output is correct |
9 |
Correct |
628 ms |
118044 KB |
Output is correct |
10 |
Correct |
619 ms |
118964 KB |
Output is correct |
11 |
Correct |
954 ms |
119752 KB |
Output is correct |
12 |
Correct |
919 ms |
119888 KB |
Output is correct |
13 |
Correct |
970 ms |
120396 KB |
Output is correct |
14 |
Correct |
1138 ms |
120064 KB |
Output is correct |
15 |
Correct |
1192 ms |
120872 KB |
Output is correct |
16 |
Correct |
1271 ms |
122128 KB |
Output is correct |
17 |
Correct |
1270 ms |
123060 KB |
Output is correct |
18 |
Correct |
1269 ms |
122780 KB |
Output is correct |
19 |
Correct |
1242 ms |
123388 KB |
Output is correct |
20 |
Correct |
1070 ms |
120224 KB |
Output is correct |
21 |
Correct |
1057 ms |
120836 KB |
Output is correct |
22 |
Correct |
1201 ms |
121136 KB |
Output is correct |
23 |
Correct |
1036 ms |
110596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1067 ms |
255844 KB |
Output is correct |
2 |
Correct |
1088 ms |
254096 KB |
Output is correct |
3 |
Correct |
1055 ms |
254520 KB |
Output is correct |
4 |
Correct |
1073 ms |
253980 KB |
Output is correct |
5 |
Correct |
1062 ms |
254920 KB |
Output is correct |
6 |
Correct |
1273 ms |
421164 KB |
Output is correct |
7 |
Correct |
1276 ms |
401208 KB |
Output is correct |
8 |
Correct |
1278 ms |
410164 KB |
Output is correct |
9 |
Correct |
37 ms |
33584 KB |
Output is correct |
10 |
Correct |
915 ms |
344108 KB |
Output is correct |
11 |
Correct |
914 ms |
316964 KB |
Output is correct |
12 |
Correct |
838 ms |
209384 KB |
Output is correct |
13 |
Correct |
848 ms |
196492 KB |
Output is correct |
14 |
Correct |
809 ms |
227360 KB |
Output is correct |
15 |
Correct |
571 ms |
265560 KB |
Output is correct |
16 |
Correct |
894 ms |
303008 KB |
Output is correct |
17 |
Correct |
791 ms |
225564 KB |
Output is correct |
18 |
Correct |
38 ms |
33616 KB |
Output is correct |
19 |
Correct |
862 ms |
264972 KB |
Output is correct |
20 |
Correct |
744 ms |
211936 KB |
Output is correct |
21 |
Correct |
661 ms |
177788 KB |
Output is correct |
22 |
Correct |
562 ms |
158344 KB |
Output is correct |
23 |
Correct |
522 ms |
135452 KB |
Output is correct |
24 |
Correct |
566 ms |
153292 KB |
Output is correct |
25 |
Correct |
511 ms |
131876 KB |
Output is correct |
26 |
Correct |
1047 ms |
254500 KB |
Output is correct |
27 |
Correct |
1183 ms |
336132 KB |
Output is correct |
28 |
Correct |
1083 ms |
250964 KB |
Output is correct |
29 |
Correct |
805 ms |
162840 KB |
Output is correct |
30 |
Correct |
1177 ms |
297508 KB |
Output is correct |
31 |
Correct |
1209 ms |
305280 KB |
Output is correct |
32 |
Correct |
1193 ms |
306460 KB |
Output is correct |
33 |
Correct |
1055 ms |
252120 KB |
Output is correct |
34 |
Correct |
1102 ms |
251484 KB |
Output is correct |
35 |
Correct |
1083 ms |
252180 KB |
Output is correct |
36 |
Correct |
871 ms |
175668 KB |
Output is correct |
37 |
Correct |
857 ms |
173152 KB |
Output is correct |
38 |
Correct |
849 ms |
169684 KB |
Output is correct |
39 |
Correct |
724 ms |
141032 KB |
Output is correct |
40 |
Correct |
724 ms |
140120 KB |
Output is correct |
41 |
Correct |
710 ms |
138724 KB |
Output is correct |
42 |
Correct |
696 ms |
136652 KB |
Output is correct |
43 |
Correct |
711 ms |
134952 KB |
Output is correct |
44 |
Correct |
706 ms |
133160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
30040 KB |
Output is correct |
2 |
Correct |
9 ms |
30044 KB |
Output is correct |
3 |
Correct |
39 ms |
43856 KB |
Output is correct |
4 |
Correct |
11 ms |
28260 KB |
Output is correct |
5 |
Correct |
39 ms |
46416 KB |
Output is correct |
6 |
Correct |
44 ms |
46172 KB |
Output is correct |
7 |
Correct |
36 ms |
47440 KB |
Output is correct |
8 |
Correct |
40 ms |
42456 KB |
Output is correct |
9 |
Correct |
53 ms |
60244 KB |
Output is correct |
10 |
Correct |
41 ms |
44368 KB |
Output is correct |
11 |
Correct |
41 ms |
43728 KB |
Output is correct |
12 |
Correct |
62 ms |
48516 KB |
Output is correct |
13 |
Correct |
45 ms |
45396 KB |
Output is correct |
14 |
Correct |
45 ms |
43344 KB |
Output is correct |
15 |
Correct |
47 ms |
45004 KB |
Output is correct |
16 |
Correct |
51 ms |
52816 KB |
Output is correct |
17 |
Correct |
46 ms |
50000 KB |
Output is correct |
18 |
Correct |
1067 ms |
255844 KB |
Output is correct |
19 |
Correct |
1088 ms |
254096 KB |
Output is correct |
20 |
Correct |
1055 ms |
254520 KB |
Output is correct |
21 |
Correct |
1073 ms |
253980 KB |
Output is correct |
22 |
Correct |
1062 ms |
254920 KB |
Output is correct |
23 |
Correct |
1273 ms |
421164 KB |
Output is correct |
24 |
Correct |
1276 ms |
401208 KB |
Output is correct |
25 |
Correct |
1278 ms |
410164 KB |
Output is correct |
26 |
Correct |
37 ms |
33584 KB |
Output is correct |
27 |
Correct |
915 ms |
344108 KB |
Output is correct |
28 |
Correct |
914 ms |
316964 KB |
Output is correct |
29 |
Correct |
838 ms |
209384 KB |
Output is correct |
30 |
Correct |
848 ms |
196492 KB |
Output is correct |
31 |
Correct |
809 ms |
227360 KB |
Output is correct |
32 |
Correct |
571 ms |
265560 KB |
Output is correct |
33 |
Correct |
894 ms |
303008 KB |
Output is correct |
34 |
Correct |
791 ms |
225564 KB |
Output is correct |
35 |
Correct |
38 ms |
33616 KB |
Output is correct |
36 |
Correct |
862 ms |
264972 KB |
Output is correct |
37 |
Correct |
744 ms |
211936 KB |
Output is correct |
38 |
Correct |
661 ms |
177788 KB |
Output is correct |
39 |
Correct |
562 ms |
158344 KB |
Output is correct |
40 |
Correct |
522 ms |
135452 KB |
Output is correct |
41 |
Correct |
566 ms |
153292 KB |
Output is correct |
42 |
Correct |
511 ms |
131876 KB |
Output is correct |
43 |
Correct |
1266 ms |
121116 KB |
Output is correct |
44 |
Correct |
36 ms |
33764 KB |
Output is correct |
45 |
Correct |
146 ms |
36804 KB |
Output is correct |
46 |
Correct |
104 ms |
36916 KB |
Output is correct |
47 |
Correct |
1209 ms |
120004 KB |
Output is correct |
48 |
Correct |
1240 ms |
121388 KB |
Output is correct |
49 |
Correct |
1241 ms |
119640 KB |
Output is correct |
50 |
Correct |
629 ms |
117984 KB |
Output is correct |
51 |
Correct |
628 ms |
118044 KB |
Output is correct |
52 |
Correct |
619 ms |
118964 KB |
Output is correct |
53 |
Correct |
954 ms |
119752 KB |
Output is correct |
54 |
Correct |
919 ms |
119888 KB |
Output is correct |
55 |
Correct |
970 ms |
120396 KB |
Output is correct |
56 |
Correct |
1138 ms |
120064 KB |
Output is correct |
57 |
Correct |
1192 ms |
120872 KB |
Output is correct |
58 |
Correct |
1271 ms |
122128 KB |
Output is correct |
59 |
Correct |
1270 ms |
123060 KB |
Output is correct |
60 |
Correct |
1269 ms |
122780 KB |
Output is correct |
61 |
Correct |
1242 ms |
123388 KB |
Output is correct |
62 |
Correct |
1070 ms |
120224 KB |
Output is correct |
63 |
Correct |
1057 ms |
120836 KB |
Output is correct |
64 |
Correct |
1201 ms |
121136 KB |
Output is correct |
65 |
Correct |
1036 ms |
110596 KB |
Output is correct |
66 |
Correct |
1047 ms |
254500 KB |
Output is correct |
67 |
Correct |
1183 ms |
336132 KB |
Output is correct |
68 |
Correct |
1083 ms |
250964 KB |
Output is correct |
69 |
Correct |
805 ms |
162840 KB |
Output is correct |
70 |
Correct |
1177 ms |
297508 KB |
Output is correct |
71 |
Correct |
1209 ms |
305280 KB |
Output is correct |
72 |
Correct |
1193 ms |
306460 KB |
Output is correct |
73 |
Correct |
1055 ms |
252120 KB |
Output is correct |
74 |
Correct |
1102 ms |
251484 KB |
Output is correct |
75 |
Correct |
1083 ms |
252180 KB |
Output is correct |
76 |
Correct |
871 ms |
175668 KB |
Output is correct |
77 |
Correct |
857 ms |
173152 KB |
Output is correct |
78 |
Correct |
849 ms |
169684 KB |
Output is correct |
79 |
Correct |
724 ms |
141032 KB |
Output is correct |
80 |
Correct |
724 ms |
140120 KB |
Output is correct |
81 |
Correct |
710 ms |
138724 KB |
Output is correct |
82 |
Correct |
696 ms |
136652 KB |
Output is correct |
83 |
Correct |
711 ms |
134952 KB |
Output is correct |
84 |
Correct |
706 ms |
133160 KB |
Output is correct |
85 |
Correct |
1582 ms |
258904 KB |
Output is correct |
86 |
Correct |
166 ms |
49456 KB |
Output is correct |
87 |
Correct |
116 ms |
59396 KB |
Output is correct |
88 |
Correct |
1472 ms |
298544 KB |
Output is correct |
89 |
Correct |
1581 ms |
255328 KB |
Output is correct |
90 |
Correct |
1503 ms |
312448 KB |
Output is correct |
91 |
Correct |
1108 ms |
255300 KB |
Output is correct |
92 |
Correct |
1103 ms |
254016 KB |
Output is correct |
93 |
Correct |
1361 ms |
349240 KB |
Output is correct |
94 |
Correct |
1319 ms |
256108 KB |
Output is correct |
95 |
Correct |
1314 ms |
255876 KB |
Output is correct |
96 |
Correct |
1367 ms |
358964 KB |
Output is correct |
97 |
Correct |
1312 ms |
185840 KB |
Output is correct |
98 |
Correct |
1285 ms |
180032 KB |
Output is correct |
99 |
Correct |
1601 ms |
261252 KB |
Output is correct |
100 |
Correct |
1601 ms |
258732 KB |
Output is correct |
101 |
Correct |
1665 ms |
259328 KB |
Output is correct |
102 |
Correct |
1611 ms |
259256 KB |
Output is correct |
103 |
Correct |
1504 ms |
383632 KB |
Output is correct |
104 |
Correct |
1535 ms |
383820 KB |
Output is correct |
105 |
Correct |
1208 ms |
199520 KB |
Output is correct |
106 |
Correct |
1031 ms |
160092 KB |
Output is correct |
107 |
Correct |
1256 ms |
211204 KB |
Output is correct |
108 |
Correct |
1566 ms |
327904 KB |
Output is correct |
109 |
Correct |
1387 ms |
343204 KB |
Output is correct |