# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
905934 |
2024-01-13T07:25:18 Z |
Boycl07 |
Bridges (APIO19_bridges) |
C++17 |
|
2831 ms |
10592 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task ""
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
inline int readInt() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
const int N = 1e5 + 10;
const int M = 1e3 + 3;
const int N1 = 2e3 + 10;
const int K = 1e2 + 1;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const ll LINF = 1e17 + 2;
const int block_size = 500;
const int LOG = 29;
const int offset = N;
const int LIM = 1e4 ;
const int AL = 26;
int n, m, q;
const int S = 400;
struct Dsu_rollback
{
int par[N], sz[N];
int cur = 0;
pii st[2 * N];
void init(int n_)
{
rep(i, n_) par[i] = i, sz[i] = 1;
cur = 0;
}
int find_set(int u)
{
while(u != par[u]) u = par[u]; return u;
}
void union_set(int u, int v)
{
if((u = find_set(u)) == (v = find_set(v))) return;
st[++cur] = {u, sz[u]};
st[++cur] = {v, sz[v]};
if(sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
}
void roll_back(int lst)
{
while(cur > lst)
{
int u = st[cur].fi, sz_u = st[cur].se;
par[u] = u;
sz[u] = sz_u;
--cur;
}
}
} dsu;
bool ch[N];
vector<int> unchanged_edges;
vector<int> changed_edges;
vector<int> queries;
vector<int> g[S + 2];
int u[N], v[N], w[N];
int t[N], x[N], y[N];
int ans[N];
void solve()
{
cin >> n >> m;
rep(i, m) cin >> u[i] >> v[i] >> w[i];
cin >> q;
rep(i, q) cin >> t[i] >> x[i] >> y[i];
for(int l = 1; l <= q; l += S)
{
dsu.init(n);
changed_edges.clear();
unchanged_edges.clear();
queries.clear();
int r = min(l + S - 1, q);
rep(i, m) ch[i] = 0;
forn(i, l, r)
{
if(t[i] == 1) ch[x[i]] = 1;
else
queries.pb(i);
g[i - l].clear();
}
rep(i, m) if(ch[i]) changed_edges.pb(i);
else unchanged_edges.pb(i);
sort(all(unchanged_edges), [] (const int &a, const int &b) {
return w[a] > w[b];
});
sort(all(queries), [] (const int &a, const int &b) {
return y[a] > y[b];
});
forn(i, l, r)
if(t[i] == 1)
w[x[i]] = y[i];
else
for(int j : changed_edges)
if(w[j] >= y[i])
g[i - l].pb(j);
int j = 0;
for(int i : queries)
{
while(j < sz(unchanged_edges) && w[unchanged_edges[j]] >= y[i])
{
int idx = unchanged_edges[j];
dsu.union_set(u[idx], v[idx]);
++j;
}
int lst = dsu.cur;
for(int t : g[i - l])
dsu.union_set(u[t], v[t]);
ans[i] = dsu.sz[dsu.find_set(x[i])];
dsu.roll_back(lst);
}
}
rep(i, q) if(t[i] == 2) cout << ans[i] << endl;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int TC = 1;
while(TC--)
{
solve();
cout << endl;
}
return 0;
}
//ha
Compilation message
bridges.cpp: In member function 'int Dsu_rollback::find_set(int)':
bridges.cpp:64:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
64 | while(u != par[u]) u = par[u]; return u;
| ^~~~~
bridges.cpp:64:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
64 | while(u != par[u]) u = par[u]; return u;
| ^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5464 KB |
Output is correct |
2 |
Correct |
2 ms |
5468 KB |
Output is correct |
3 |
Correct |
13 ms |
5980 KB |
Output is correct |
4 |
Correct |
4 ms |
5468 KB |
Output is correct |
5 |
Correct |
8 ms |
5724 KB |
Output is correct |
6 |
Correct |
6 ms |
5720 KB |
Output is correct |
7 |
Correct |
7 ms |
5720 KB |
Output is correct |
8 |
Correct |
8 ms |
5724 KB |
Output is correct |
9 |
Correct |
9 ms |
5720 KB |
Output is correct |
10 |
Correct |
7 ms |
5724 KB |
Output is correct |
11 |
Correct |
7 ms |
5720 KB |
Output is correct |
12 |
Correct |
8 ms |
5720 KB |
Output is correct |
13 |
Correct |
10 ms |
5752 KB |
Output is correct |
14 |
Correct |
9 ms |
5720 KB |
Output is correct |
15 |
Correct |
9 ms |
5724 KB |
Output is correct |
16 |
Correct |
7 ms |
5724 KB |
Output is correct |
17 |
Correct |
7 ms |
5724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1277 ms |
6580 KB |
Output is correct |
2 |
Correct |
1300 ms |
6300 KB |
Output is correct |
3 |
Correct |
1283 ms |
6376 KB |
Output is correct |
4 |
Correct |
1317 ms |
6296 KB |
Output is correct |
5 |
Correct |
1240 ms |
6396 KB |
Output is correct |
6 |
Correct |
1378 ms |
6508 KB |
Output is correct |
7 |
Correct |
1392 ms |
6500 KB |
Output is correct |
8 |
Correct |
1371 ms |
6500 KB |
Output is correct |
9 |
Correct |
30 ms |
5720 KB |
Output is correct |
10 |
Correct |
603 ms |
6456 KB |
Output is correct |
11 |
Correct |
627 ms |
6372 KB |
Output is correct |
12 |
Correct |
1268 ms |
6232 KB |
Output is correct |
13 |
Correct |
1308 ms |
6656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
888 ms |
6212 KB |
Output is correct |
2 |
Correct |
303 ms |
6100 KB |
Output is correct |
3 |
Correct |
860 ms |
6288 KB |
Output is correct |
4 |
Correct |
831 ms |
6224 KB |
Output is correct |
5 |
Correct |
26 ms |
5720 KB |
Output is correct |
6 |
Correct |
838 ms |
6208 KB |
Output is correct |
7 |
Correct |
803 ms |
6224 KB |
Output is correct |
8 |
Correct |
789 ms |
6224 KB |
Output is correct |
9 |
Correct |
841 ms |
6128 KB |
Output is correct |
10 |
Correct |
770 ms |
6136 KB |
Output is correct |
11 |
Correct |
789 ms |
6652 KB |
Output is correct |
12 |
Correct |
763 ms |
6668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2661 ms |
6428 KB |
Output is correct |
2 |
Correct |
26 ms |
7004 KB |
Output is correct |
3 |
Correct |
289 ms |
8372 KB |
Output is correct |
4 |
Correct |
114 ms |
7988 KB |
Output is correct |
5 |
Correct |
1278 ms |
8728 KB |
Output is correct |
6 |
Correct |
2621 ms |
10256 KB |
Output is correct |
7 |
Correct |
1315 ms |
9060 KB |
Output is correct |
8 |
Correct |
1211 ms |
8664 KB |
Output is correct |
9 |
Correct |
1205 ms |
8968 KB |
Output is correct |
10 |
Correct |
1250 ms |
8764 KB |
Output is correct |
11 |
Correct |
2012 ms |
9684 KB |
Output is correct |
12 |
Correct |
1912 ms |
9656 KB |
Output is correct |
13 |
Correct |
1988 ms |
9384 KB |
Output is correct |
14 |
Correct |
1156 ms |
8912 KB |
Output is correct |
15 |
Correct |
1234 ms |
8968 KB |
Output is correct |
16 |
Correct |
2708 ms |
10172 KB |
Output is correct |
17 |
Correct |
2738 ms |
10152 KB |
Output is correct |
18 |
Correct |
2718 ms |
10412 KB |
Output is correct |
19 |
Correct |
2656 ms |
10452 KB |
Output is correct |
20 |
Correct |
2258 ms |
9936 KB |
Output is correct |
21 |
Correct |
2223 ms |
9748 KB |
Output is correct |
22 |
Correct |
2626 ms |
10216 KB |
Output is correct |
23 |
Correct |
1459 ms |
8824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1277 ms |
6580 KB |
Output is correct |
2 |
Correct |
1300 ms |
6300 KB |
Output is correct |
3 |
Correct |
1283 ms |
6376 KB |
Output is correct |
4 |
Correct |
1317 ms |
6296 KB |
Output is correct |
5 |
Correct |
1240 ms |
6396 KB |
Output is correct |
6 |
Correct |
1378 ms |
6508 KB |
Output is correct |
7 |
Correct |
1392 ms |
6500 KB |
Output is correct |
8 |
Correct |
1371 ms |
6500 KB |
Output is correct |
9 |
Correct |
30 ms |
5720 KB |
Output is correct |
10 |
Correct |
603 ms |
6456 KB |
Output is correct |
11 |
Correct |
627 ms |
6372 KB |
Output is correct |
12 |
Correct |
1268 ms |
6232 KB |
Output is correct |
13 |
Correct |
1308 ms |
6656 KB |
Output is correct |
14 |
Correct |
888 ms |
6212 KB |
Output is correct |
15 |
Correct |
303 ms |
6100 KB |
Output is correct |
16 |
Correct |
860 ms |
6288 KB |
Output is correct |
17 |
Correct |
831 ms |
6224 KB |
Output is correct |
18 |
Correct |
26 ms |
5720 KB |
Output is correct |
19 |
Correct |
838 ms |
6208 KB |
Output is correct |
20 |
Correct |
803 ms |
6224 KB |
Output is correct |
21 |
Correct |
789 ms |
6224 KB |
Output is correct |
22 |
Correct |
841 ms |
6128 KB |
Output is correct |
23 |
Correct |
770 ms |
6136 KB |
Output is correct |
24 |
Correct |
789 ms |
6652 KB |
Output is correct |
25 |
Correct |
763 ms |
6668 KB |
Output is correct |
26 |
Correct |
1248 ms |
6356 KB |
Output is correct |
27 |
Correct |
1337 ms |
6616 KB |
Output is correct |
28 |
Correct |
1328 ms |
6456 KB |
Output is correct |
29 |
Correct |
1240 ms |
6356 KB |
Output is correct |
30 |
Correct |
1311 ms |
6360 KB |
Output is correct |
31 |
Correct |
1343 ms |
6516 KB |
Output is correct |
32 |
Correct |
1351 ms |
6464 KB |
Output is correct |
33 |
Correct |
1298 ms |
6356 KB |
Output is correct |
34 |
Correct |
1326 ms |
6500 KB |
Output is correct |
35 |
Correct |
1319 ms |
6512 KB |
Output is correct |
36 |
Correct |
1272 ms |
6308 KB |
Output is correct |
37 |
Correct |
1276 ms |
6208 KB |
Output is correct |
38 |
Correct |
1276 ms |
6300 KB |
Output is correct |
39 |
Correct |
1240 ms |
6096 KB |
Output is correct |
40 |
Correct |
1243 ms |
5932 KB |
Output is correct |
41 |
Correct |
1248 ms |
6176 KB |
Output is correct |
42 |
Correct |
1176 ms |
6612 KB |
Output is correct |
43 |
Correct |
1221 ms |
6572 KB |
Output is correct |
44 |
Correct |
1175 ms |
6752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5464 KB |
Output is correct |
2 |
Correct |
2 ms |
5468 KB |
Output is correct |
3 |
Correct |
13 ms |
5980 KB |
Output is correct |
4 |
Correct |
4 ms |
5468 KB |
Output is correct |
5 |
Correct |
8 ms |
5724 KB |
Output is correct |
6 |
Correct |
6 ms |
5720 KB |
Output is correct |
7 |
Correct |
7 ms |
5720 KB |
Output is correct |
8 |
Correct |
8 ms |
5724 KB |
Output is correct |
9 |
Correct |
9 ms |
5720 KB |
Output is correct |
10 |
Correct |
7 ms |
5724 KB |
Output is correct |
11 |
Correct |
7 ms |
5720 KB |
Output is correct |
12 |
Correct |
8 ms |
5720 KB |
Output is correct |
13 |
Correct |
10 ms |
5752 KB |
Output is correct |
14 |
Correct |
9 ms |
5720 KB |
Output is correct |
15 |
Correct |
9 ms |
5724 KB |
Output is correct |
16 |
Correct |
7 ms |
5724 KB |
Output is correct |
17 |
Correct |
7 ms |
5724 KB |
Output is correct |
18 |
Correct |
1277 ms |
6580 KB |
Output is correct |
19 |
Correct |
1300 ms |
6300 KB |
Output is correct |
20 |
Correct |
1283 ms |
6376 KB |
Output is correct |
21 |
Correct |
1317 ms |
6296 KB |
Output is correct |
22 |
Correct |
1240 ms |
6396 KB |
Output is correct |
23 |
Correct |
1378 ms |
6508 KB |
Output is correct |
24 |
Correct |
1392 ms |
6500 KB |
Output is correct |
25 |
Correct |
1371 ms |
6500 KB |
Output is correct |
26 |
Correct |
30 ms |
5720 KB |
Output is correct |
27 |
Correct |
603 ms |
6456 KB |
Output is correct |
28 |
Correct |
627 ms |
6372 KB |
Output is correct |
29 |
Correct |
1268 ms |
6232 KB |
Output is correct |
30 |
Correct |
1308 ms |
6656 KB |
Output is correct |
31 |
Correct |
888 ms |
6212 KB |
Output is correct |
32 |
Correct |
303 ms |
6100 KB |
Output is correct |
33 |
Correct |
860 ms |
6288 KB |
Output is correct |
34 |
Correct |
831 ms |
6224 KB |
Output is correct |
35 |
Correct |
26 ms |
5720 KB |
Output is correct |
36 |
Correct |
838 ms |
6208 KB |
Output is correct |
37 |
Correct |
803 ms |
6224 KB |
Output is correct |
38 |
Correct |
789 ms |
6224 KB |
Output is correct |
39 |
Correct |
841 ms |
6128 KB |
Output is correct |
40 |
Correct |
770 ms |
6136 KB |
Output is correct |
41 |
Correct |
789 ms |
6652 KB |
Output is correct |
42 |
Correct |
763 ms |
6668 KB |
Output is correct |
43 |
Correct |
2661 ms |
6428 KB |
Output is correct |
44 |
Correct |
26 ms |
7004 KB |
Output is correct |
45 |
Correct |
289 ms |
8372 KB |
Output is correct |
46 |
Correct |
114 ms |
7988 KB |
Output is correct |
47 |
Correct |
1278 ms |
8728 KB |
Output is correct |
48 |
Correct |
2621 ms |
10256 KB |
Output is correct |
49 |
Correct |
1315 ms |
9060 KB |
Output is correct |
50 |
Correct |
1211 ms |
8664 KB |
Output is correct |
51 |
Correct |
1205 ms |
8968 KB |
Output is correct |
52 |
Correct |
1250 ms |
8764 KB |
Output is correct |
53 |
Correct |
2012 ms |
9684 KB |
Output is correct |
54 |
Correct |
1912 ms |
9656 KB |
Output is correct |
55 |
Correct |
1988 ms |
9384 KB |
Output is correct |
56 |
Correct |
1156 ms |
8912 KB |
Output is correct |
57 |
Correct |
1234 ms |
8968 KB |
Output is correct |
58 |
Correct |
2708 ms |
10172 KB |
Output is correct |
59 |
Correct |
2738 ms |
10152 KB |
Output is correct |
60 |
Correct |
2718 ms |
10412 KB |
Output is correct |
61 |
Correct |
2656 ms |
10452 KB |
Output is correct |
62 |
Correct |
2258 ms |
9936 KB |
Output is correct |
63 |
Correct |
2223 ms |
9748 KB |
Output is correct |
64 |
Correct |
2626 ms |
10216 KB |
Output is correct |
65 |
Correct |
1459 ms |
8824 KB |
Output is correct |
66 |
Correct |
1248 ms |
6356 KB |
Output is correct |
67 |
Correct |
1337 ms |
6616 KB |
Output is correct |
68 |
Correct |
1328 ms |
6456 KB |
Output is correct |
69 |
Correct |
1240 ms |
6356 KB |
Output is correct |
70 |
Correct |
1311 ms |
6360 KB |
Output is correct |
71 |
Correct |
1343 ms |
6516 KB |
Output is correct |
72 |
Correct |
1351 ms |
6464 KB |
Output is correct |
73 |
Correct |
1298 ms |
6356 KB |
Output is correct |
74 |
Correct |
1326 ms |
6500 KB |
Output is correct |
75 |
Correct |
1319 ms |
6512 KB |
Output is correct |
76 |
Correct |
1272 ms |
6308 KB |
Output is correct |
77 |
Correct |
1276 ms |
6208 KB |
Output is correct |
78 |
Correct |
1276 ms |
6300 KB |
Output is correct |
79 |
Correct |
1240 ms |
6096 KB |
Output is correct |
80 |
Correct |
1243 ms |
5932 KB |
Output is correct |
81 |
Correct |
1248 ms |
6176 KB |
Output is correct |
82 |
Correct |
1176 ms |
6612 KB |
Output is correct |
83 |
Correct |
1221 ms |
6572 KB |
Output is correct |
84 |
Correct |
1175 ms |
6752 KB |
Output is correct |
85 |
Correct |
2729 ms |
10508 KB |
Output is correct |
86 |
Correct |
296 ms |
8408 KB |
Output is correct |
87 |
Correct |
131 ms |
8148 KB |
Output is correct |
88 |
Correct |
1480 ms |
8784 KB |
Output is correct |
89 |
Correct |
2796 ms |
10592 KB |
Output is correct |
90 |
Correct |
1344 ms |
9032 KB |
Output is correct |
91 |
Correct |
1313 ms |
8984 KB |
Output is correct |
92 |
Correct |
1307 ms |
9176 KB |
Output is correct |
93 |
Correct |
1379 ms |
9176 KB |
Output is correct |
94 |
Correct |
2122 ms |
10040 KB |
Output is correct |
95 |
Correct |
2045 ms |
9748 KB |
Output is correct |
96 |
Correct |
2077 ms |
9608 KB |
Output is correct |
97 |
Correct |
1313 ms |
8932 KB |
Output is correct |
98 |
Correct |
1309 ms |
9428 KB |
Output is correct |
99 |
Correct |
2794 ms |
10248 KB |
Output is correct |
100 |
Correct |
2831 ms |
10284 KB |
Output is correct |
101 |
Correct |
2794 ms |
10428 KB |
Output is correct |
102 |
Correct |
2796 ms |
10476 KB |
Output is correct |
103 |
Correct |
2370 ms |
9916 KB |
Output is correct |
104 |
Correct |
2394 ms |
9872 KB |
Output is correct |
105 |
Correct |
2276 ms |
10360 KB |
Output is correct |
106 |
Correct |
1981 ms |
9952 KB |
Output is correct |
107 |
Correct |
2279 ms |
9592 KB |
Output is correct |
108 |
Correct |
2658 ms |
10300 KB |
Output is correct |
109 |
Correct |
1499 ms |
8540 KB |
Output is correct |