#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
void program();
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
program();
}
//===================//
// begin program //
//===================//
const int MX = 1e5+10;
const int N = (1<<20);
const int SQ = 700;
int n, m;
int u[MX], v[MX], d[MX], tempD[MX];
int q;
int t[MX], b[MX], nd[MX], s[MX], w[MX];
int ans[MX];
// dsu
int p[MX], sz[MX];
stack<int> stck;
void buildDSU(int dsuSize) {
RE(i,dsuSize) p[i]=i, sz[i]=1;
while(!stck.empty()) stck.pop();
}
int getSet(int i) {return i==p[i]?i:getSet(p[i]);}
bool isSameSet(int i, int j) {return getSet(i)==getSet(j);}
void unionSet(int i, int j) {
i = getSet(i); j = getSet(j);
if(i != j) {
if(sz[i] < sz[j]) swap(i,j);
sz[i] = sz[i] + sz[j];
p[j] = i;
stck.push(j);
} else {
stck.push(-1);
}
}
void unionUndo() {
int u = stck.top(); stck.pop();
if(u == -1) return;
sz[p[u]] -= sz[u];
p[u] = u;
}
bitset<MX> used;
vi inBlock[SQ];
void program() {
IN(n,m);
RE(i,m) IN(u[i],v[i],d[i]);
IN(q);
RE(i,q) {
IN(t[i]);
if(t[i] == 1) IN(b[i],nd[i]), b[i]--;
if(t[i] == 2) IN(s[i],w[i]);
}
RE(i,q) inBlock[i/SQ].pb(i);
RE(cb,SQ) {
if(inBlock[cb].empty()) break;
used.reset();
vi impEdges;
vi changes;
vii queries;
FOR(i,inBlock[cb]) {
if(t[i] == 1) {
impEdges.pb(b[i]);
used[b[i]] = 1;
changes.pb(i);
}
if(t[i] == 2) queries.pb({w[i],i});
}
sort(all(queries),greater<ii>());
viii edges;
RE(i,m) if(!used[i]) edges.pb({d[i],u[i],v[i]});
sort(all(edges),greater<iii>());
buildDSU(n+1);
int cq = 0;
auto answerQuery = [&](int i) {
FOR(u,impEdges) tempD[u] = d[u];
FOR(j,changes) {
if(j >= i) break;
if(t[j] == 1) tempD[b[j]] = nd[j];
}
int undos = 0;
FOR(j,impEdges)
if(tempD[j] >= w[i])
unionSet(u[j],v[j]), undos++;
ans[i] = sz[getSet(s[i])];
RE(_,undos)
unionUndo();
};
FOR(p,edges) {
int cd, u, v;
tie(cd,u,v) = p;
while(cq != queries.size() && queries[cq].fi > cd)
answerQuery(queries[cq++].se);
unionSet(u,v);
}
while(cq != queries.size())
answerQuery(queries[cq++].se);
// update distances for next block
FOR(i,inBlock[cb]) if(t[i] == 1) d[b[i]] = nd[i];
}
RE(i,q) if(t[i] == 2) OUTL(ans[i]);
}
Compilation message
bridges.cpp: In function 'void program()':
bridges.cpp:154:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | while(cq != queries.size() && queries[cq].fi > cd)
| ~~~^~~~~~~~~~~~~~~~~
bridges.cpp:158:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | while(cq != queries.size())
| ~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
40 ms |
740 KB |
Output is correct |
4 |
Correct |
5 ms |
588 KB |
Output is correct |
5 |
Correct |
39 ms |
708 KB |
Output is correct |
6 |
Correct |
32 ms |
712 KB |
Output is correct |
7 |
Correct |
36 ms |
720 KB |
Output is correct |
8 |
Correct |
39 ms |
716 KB |
Output is correct |
9 |
Correct |
43 ms |
700 KB |
Output is correct |
10 |
Correct |
39 ms |
708 KB |
Output is correct |
11 |
Correct |
40 ms |
704 KB |
Output is correct |
12 |
Correct |
46 ms |
704 KB |
Output is correct |
13 |
Correct |
45 ms |
708 KB |
Output is correct |
14 |
Correct |
41 ms |
720 KB |
Output is correct |
15 |
Correct |
45 ms |
700 KB |
Output is correct |
16 |
Correct |
42 ms |
708 KB |
Output is correct |
17 |
Correct |
43 ms |
720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1586 ms |
6112 KB |
Output is correct |
2 |
Correct |
1610 ms |
6156 KB |
Output is correct |
3 |
Correct |
1617 ms |
6152 KB |
Output is correct |
4 |
Correct |
1646 ms |
6168 KB |
Output is correct |
5 |
Correct |
1632 ms |
6144 KB |
Output is correct |
6 |
Correct |
2206 ms |
6320 KB |
Output is correct |
7 |
Correct |
2178 ms |
6272 KB |
Output is correct |
8 |
Correct |
2179 ms |
6396 KB |
Output is correct |
9 |
Correct |
41 ms |
2696 KB |
Output is correct |
10 |
Correct |
1556 ms |
6396 KB |
Output is correct |
11 |
Correct |
1588 ms |
6072 KB |
Output is correct |
12 |
Correct |
1438 ms |
6444 KB |
Output is correct |
13 |
Correct |
1438 ms |
6168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1209 ms |
5096 KB |
Output is correct |
2 |
Correct |
807 ms |
3816 KB |
Output is correct |
3 |
Correct |
1395 ms |
5404 KB |
Output is correct |
4 |
Correct |
1190 ms |
5420 KB |
Output is correct |
5 |
Correct |
41 ms |
2628 KB |
Output is correct |
6 |
Correct |
1304 ms |
5148 KB |
Output is correct |
7 |
Correct |
1123 ms |
4960 KB |
Output is correct |
8 |
Correct |
1035 ms |
5268 KB |
Output is correct |
9 |
Correct |
862 ms |
4952 KB |
Output is correct |
10 |
Correct |
816 ms |
4992 KB |
Output is correct |
11 |
Correct |
887 ms |
5060 KB |
Output is correct |
12 |
Correct |
819 ms |
4936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2273 ms |
7200 KB |
Output is correct |
2 |
Correct |
45 ms |
4036 KB |
Output is correct |
3 |
Correct |
244 ms |
6900 KB |
Output is correct |
4 |
Correct |
253 ms |
6896 KB |
Output is correct |
5 |
Correct |
2441 ms |
9500 KB |
Output is correct |
6 |
Correct |
2172 ms |
11020 KB |
Output is correct |
7 |
Correct |
2521 ms |
9592 KB |
Output is correct |
8 |
Correct |
1054 ms |
7756 KB |
Output is correct |
9 |
Correct |
1049 ms |
8004 KB |
Output is correct |
10 |
Correct |
1053 ms |
7820 KB |
Output is correct |
11 |
Correct |
1694 ms |
9764 KB |
Output is correct |
12 |
Correct |
1647 ms |
9868 KB |
Output is correct |
13 |
Correct |
1710 ms |
9788 KB |
Output is correct |
14 |
Correct |
2393 ms |
9632 KB |
Output is correct |
15 |
Correct |
2521 ms |
9728 KB |
Output is correct |
16 |
Correct |
2261 ms |
11032 KB |
Output is correct |
17 |
Correct |
2272 ms |
11084 KB |
Output is correct |
18 |
Correct |
2268 ms |
11276 KB |
Output is correct |
19 |
Correct |
2280 ms |
11068 KB |
Output is correct |
20 |
Correct |
1918 ms |
10104 KB |
Output is correct |
21 |
Correct |
1913 ms |
10152 KB |
Output is correct |
22 |
Correct |
2178 ms |
10736 KB |
Output is correct |
23 |
Correct |
2032 ms |
8792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1586 ms |
6112 KB |
Output is correct |
2 |
Correct |
1610 ms |
6156 KB |
Output is correct |
3 |
Correct |
1617 ms |
6152 KB |
Output is correct |
4 |
Correct |
1646 ms |
6168 KB |
Output is correct |
5 |
Correct |
1632 ms |
6144 KB |
Output is correct |
6 |
Correct |
2206 ms |
6320 KB |
Output is correct |
7 |
Correct |
2178 ms |
6272 KB |
Output is correct |
8 |
Correct |
2179 ms |
6396 KB |
Output is correct |
9 |
Correct |
41 ms |
2696 KB |
Output is correct |
10 |
Correct |
1556 ms |
6396 KB |
Output is correct |
11 |
Correct |
1588 ms |
6072 KB |
Output is correct |
12 |
Correct |
1438 ms |
6444 KB |
Output is correct |
13 |
Correct |
1438 ms |
6168 KB |
Output is correct |
14 |
Correct |
1209 ms |
5096 KB |
Output is correct |
15 |
Correct |
807 ms |
3816 KB |
Output is correct |
16 |
Correct |
1395 ms |
5404 KB |
Output is correct |
17 |
Correct |
1190 ms |
5420 KB |
Output is correct |
18 |
Correct |
41 ms |
2628 KB |
Output is correct |
19 |
Correct |
1304 ms |
5148 KB |
Output is correct |
20 |
Correct |
1123 ms |
4960 KB |
Output is correct |
21 |
Correct |
1035 ms |
5268 KB |
Output is correct |
22 |
Correct |
862 ms |
4952 KB |
Output is correct |
23 |
Correct |
816 ms |
4992 KB |
Output is correct |
24 |
Correct |
887 ms |
5060 KB |
Output is correct |
25 |
Correct |
819 ms |
4936 KB |
Output is correct |
26 |
Correct |
1609 ms |
6068 KB |
Output is correct |
27 |
Correct |
1886 ms |
6076 KB |
Output is correct |
28 |
Correct |
1660 ms |
6060 KB |
Output is correct |
29 |
Correct |
1363 ms |
6168 KB |
Output is correct |
30 |
Correct |
1822 ms |
6028 KB |
Output is correct |
31 |
Correct |
1860 ms |
6048 KB |
Output is correct |
32 |
Correct |
1866 ms |
6040 KB |
Output is correct |
33 |
Correct |
1661 ms |
6040 KB |
Output is correct |
34 |
Correct |
1675 ms |
6336 KB |
Output is correct |
35 |
Correct |
1663 ms |
6304 KB |
Output is correct |
36 |
Correct |
1410 ms |
6180 KB |
Output is correct |
37 |
Correct |
1403 ms |
6136 KB |
Output is correct |
38 |
Correct |
1399 ms |
6168 KB |
Output is correct |
39 |
Correct |
1184 ms |
6244 KB |
Output is correct |
40 |
Correct |
1164 ms |
6220 KB |
Output is correct |
41 |
Correct |
1225 ms |
6244 KB |
Output is correct |
42 |
Correct |
1178 ms |
6116 KB |
Output is correct |
43 |
Correct |
1172 ms |
5996 KB |
Output is correct |
44 |
Correct |
1168 ms |
6128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
40 ms |
740 KB |
Output is correct |
4 |
Correct |
5 ms |
588 KB |
Output is correct |
5 |
Correct |
39 ms |
708 KB |
Output is correct |
6 |
Correct |
32 ms |
712 KB |
Output is correct |
7 |
Correct |
36 ms |
720 KB |
Output is correct |
8 |
Correct |
39 ms |
716 KB |
Output is correct |
9 |
Correct |
43 ms |
700 KB |
Output is correct |
10 |
Correct |
39 ms |
708 KB |
Output is correct |
11 |
Correct |
40 ms |
704 KB |
Output is correct |
12 |
Correct |
46 ms |
704 KB |
Output is correct |
13 |
Correct |
45 ms |
708 KB |
Output is correct |
14 |
Correct |
41 ms |
720 KB |
Output is correct |
15 |
Correct |
45 ms |
700 KB |
Output is correct |
16 |
Correct |
42 ms |
708 KB |
Output is correct |
17 |
Correct |
43 ms |
720 KB |
Output is correct |
18 |
Correct |
1586 ms |
6112 KB |
Output is correct |
19 |
Correct |
1610 ms |
6156 KB |
Output is correct |
20 |
Correct |
1617 ms |
6152 KB |
Output is correct |
21 |
Correct |
1646 ms |
6168 KB |
Output is correct |
22 |
Correct |
1632 ms |
6144 KB |
Output is correct |
23 |
Correct |
2206 ms |
6320 KB |
Output is correct |
24 |
Correct |
2178 ms |
6272 KB |
Output is correct |
25 |
Correct |
2179 ms |
6396 KB |
Output is correct |
26 |
Correct |
41 ms |
2696 KB |
Output is correct |
27 |
Correct |
1556 ms |
6396 KB |
Output is correct |
28 |
Correct |
1588 ms |
6072 KB |
Output is correct |
29 |
Correct |
1438 ms |
6444 KB |
Output is correct |
30 |
Correct |
1438 ms |
6168 KB |
Output is correct |
31 |
Correct |
1209 ms |
5096 KB |
Output is correct |
32 |
Correct |
807 ms |
3816 KB |
Output is correct |
33 |
Correct |
1395 ms |
5404 KB |
Output is correct |
34 |
Correct |
1190 ms |
5420 KB |
Output is correct |
35 |
Correct |
41 ms |
2628 KB |
Output is correct |
36 |
Correct |
1304 ms |
5148 KB |
Output is correct |
37 |
Correct |
1123 ms |
4960 KB |
Output is correct |
38 |
Correct |
1035 ms |
5268 KB |
Output is correct |
39 |
Correct |
862 ms |
4952 KB |
Output is correct |
40 |
Correct |
816 ms |
4992 KB |
Output is correct |
41 |
Correct |
887 ms |
5060 KB |
Output is correct |
42 |
Correct |
819 ms |
4936 KB |
Output is correct |
43 |
Correct |
2273 ms |
7200 KB |
Output is correct |
44 |
Correct |
45 ms |
4036 KB |
Output is correct |
45 |
Correct |
244 ms |
6900 KB |
Output is correct |
46 |
Correct |
253 ms |
6896 KB |
Output is correct |
47 |
Correct |
2441 ms |
9500 KB |
Output is correct |
48 |
Correct |
2172 ms |
11020 KB |
Output is correct |
49 |
Correct |
2521 ms |
9592 KB |
Output is correct |
50 |
Correct |
1054 ms |
7756 KB |
Output is correct |
51 |
Correct |
1049 ms |
8004 KB |
Output is correct |
52 |
Correct |
1053 ms |
7820 KB |
Output is correct |
53 |
Correct |
1694 ms |
9764 KB |
Output is correct |
54 |
Correct |
1647 ms |
9868 KB |
Output is correct |
55 |
Correct |
1710 ms |
9788 KB |
Output is correct |
56 |
Correct |
2393 ms |
9632 KB |
Output is correct |
57 |
Correct |
2521 ms |
9728 KB |
Output is correct |
58 |
Correct |
2261 ms |
11032 KB |
Output is correct |
59 |
Correct |
2272 ms |
11084 KB |
Output is correct |
60 |
Correct |
2268 ms |
11276 KB |
Output is correct |
61 |
Correct |
2280 ms |
11068 KB |
Output is correct |
62 |
Correct |
1918 ms |
10104 KB |
Output is correct |
63 |
Correct |
1913 ms |
10152 KB |
Output is correct |
64 |
Correct |
2178 ms |
10736 KB |
Output is correct |
65 |
Correct |
2032 ms |
8792 KB |
Output is correct |
66 |
Correct |
1609 ms |
6068 KB |
Output is correct |
67 |
Correct |
1886 ms |
6076 KB |
Output is correct |
68 |
Correct |
1660 ms |
6060 KB |
Output is correct |
69 |
Correct |
1363 ms |
6168 KB |
Output is correct |
70 |
Correct |
1822 ms |
6028 KB |
Output is correct |
71 |
Correct |
1860 ms |
6048 KB |
Output is correct |
72 |
Correct |
1866 ms |
6040 KB |
Output is correct |
73 |
Correct |
1661 ms |
6040 KB |
Output is correct |
74 |
Correct |
1675 ms |
6336 KB |
Output is correct |
75 |
Correct |
1663 ms |
6304 KB |
Output is correct |
76 |
Correct |
1410 ms |
6180 KB |
Output is correct |
77 |
Correct |
1403 ms |
6136 KB |
Output is correct |
78 |
Correct |
1399 ms |
6168 KB |
Output is correct |
79 |
Correct |
1184 ms |
6244 KB |
Output is correct |
80 |
Correct |
1164 ms |
6220 KB |
Output is correct |
81 |
Correct |
1225 ms |
6244 KB |
Output is correct |
82 |
Correct |
1178 ms |
6116 KB |
Output is correct |
83 |
Correct |
1172 ms |
5996 KB |
Output is correct |
84 |
Correct |
1168 ms |
6128 KB |
Output is correct |
85 |
Correct |
2769 ms |
12252 KB |
Output is correct |
86 |
Correct |
284 ms |
7248 KB |
Output is correct |
87 |
Correct |
283 ms |
7464 KB |
Output is correct |
88 |
Correct |
2979 ms |
10672 KB |
Output is correct |
89 |
Correct |
2774 ms |
12200 KB |
Output is correct |
90 |
Correct |
2963 ms |
10564 KB |
Output is correct |
91 |
Correct |
1718 ms |
8712 KB |
Output is correct |
92 |
Correct |
1694 ms |
8956 KB |
Output is correct |
93 |
Correct |
2211 ms |
8656 KB |
Output is correct |
94 |
Correct |
2304 ms |
10892 KB |
Output is correct |
95 |
Correct |
2260 ms |
11052 KB |
Output is correct |
96 |
Correct |
2656 ms |
10680 KB |
Output is correct |
97 |
Correct |
2630 ms |
10460 KB |
Output is correct |
98 |
Correct |
2714 ms |
10788 KB |
Output is correct |
99 |
Correct |
2852 ms |
12320 KB |
Output is correct |
100 |
Correct |
2838 ms |
12244 KB |
Output is correct |
101 |
Correct |
2829 ms |
12200 KB |
Output is correct |
102 |
Correct |
2853 ms |
12220 KB |
Output is correct |
103 |
Correct |
2932 ms |
11092 KB |
Output is correct |
104 |
Correct |
2906 ms |
11372 KB |
Output is correct |
105 |
Correct |
2260 ms |
11216 KB |
Output is correct |
106 |
Correct |
1872 ms |
10808 KB |
Output is correct |
107 |
Correct |
2231 ms |
11080 KB |
Output is correct |
108 |
Correct |
2923 ms |
11628 KB |
Output is correct |
109 |
Correct |
2824 ms |
9752 KB |
Output is correct |