# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
906759 |
2024-01-15T00:28:03 Z |
beaboss |
Bridges (APIO19_bridges) |
C++14 |
|
2102 ms |
12172 KB |
// Source: https://oj.uz/problem/view/APIO19_bridges
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
#define FOR(i, a, b) for (int i = (a); i<b; i++)
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }
const int Q = 1e5 + 10;
const int N = 5e4 + 10;
const int B = 1e3;
int t[Q], x[Q], y[Q];
int a[Q], b[Q], w[Q];
stack<vi> ops;
vi p(N, -1);
int res[Q];
int get(int cur) {
return p[cur] < 0 ? cur : get(p[cur]);
}
void unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) return;
if (-p[x] < -p[y]) swap(x, y);
ops.push({y, p[y], x});
p[x] += p[y];
p[y] = x;
// cout << ' ' << x << p[x] << endl;
}
void rollback() {
while (!ops.empty()) {
vi cur = ops.top();
ops.pop();
p[cur[0]] = cur[1];
p[cur[2]] -= cur[1];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
FOR(i, 1, m + 1) {
cin >> a[i] >> b[i] >> w[i];
}
int q;
cin >> q;
FOR(i, 1, q + 1) cin >> t[i] >> x[i] >> y[i];
for (int l = 1; l <= q; l += B+1) {
FOR(i, 1, n + 1) p[i]=-1;
// cout << l << endl;
int r = min(l + B, q);
vector<bool> changed(m + 1, false);
vpii unchanged;
vector<vi> add(r - l + 1);
vpii query;
for (int i = l; i <= r; i++) {
if (t[i] == 1) {
w[x[i]] = y[i]; // set the new weight
changed[x[i]]=true;
} else {
for (int j = l; j <= r; j++) {
if (t[j] == 1 && w[x[j]] >= y[i]) {
// cout << ' ' << i << x[j] << endl;
add[i - l].pb(x[j]); // add this new update if we can cross this bridge
}
}
query.pb({y[i], i});
}
}
FOR(i, 1, m + 1) if (!changed[i]) {
unchanged.pb({w[i], i});
}
// cout << unchanged.size() << endl;
sort(unchanged.rbegin(), unchanged.rend());
sort(query.rbegin(), query.rend());
int un_ind = 0;
for (auto ask: query) {
while (un_ind != unchanged.size() && unchanged[un_ind].f >= y[ask.s]) {
// cout << ask.s << unchanged[un_ind].s << endl;
unite(a[unchanged[un_ind].s], b[unchanged[un_ind].s]);
un_ind++;
}
while (!ops.empty()) ops.pop();
for (auto merge: add[ask.s - l]) {
// cout << ask.s << merge << endl;
unite(a[merge], b[merge]);
}
// cout << ask.s << -p[get(x[ask.s])] << endl;
res[ask.s] = -p[get(x[ask.s])];
rollback();
}
}
FOR(i, 1, q + 1) {
if (t[i] == 2) {
// cout << i << endl;
cout << res[i] << endl;
}
}
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:123: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]
123 | while (un_ind != unchanged.size() && unchanged[un_ind].f >= y[ask.s]) {
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
37 ms |
3528 KB |
Output is correct |
4 |
Correct |
18 ms |
2652 KB |
Output is correct |
5 |
Correct |
42 ms |
3672 KB |
Output is correct |
6 |
Correct |
31 ms |
3732 KB |
Output is correct |
7 |
Correct |
43 ms |
4252 KB |
Output is correct |
8 |
Correct |
49 ms |
3424 KB |
Output is correct |
9 |
Correct |
47 ms |
4688 KB |
Output is correct |
10 |
Correct |
49 ms |
3520 KB |
Output is correct |
11 |
Correct |
49 ms |
3496 KB |
Output is correct |
12 |
Correct |
61 ms |
4008 KB |
Output is correct |
13 |
Correct |
55 ms |
3416 KB |
Output is correct |
14 |
Correct |
53 ms |
3416 KB |
Output is correct |
15 |
Correct |
52 ms |
3604 KB |
Output is correct |
16 |
Correct |
43 ms |
4224 KB |
Output is correct |
17 |
Correct |
48 ms |
4008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1504 ms |
5056 KB |
Output is correct |
2 |
Correct |
1465 ms |
8448 KB |
Output is correct |
3 |
Correct |
1472 ms |
7844 KB |
Output is correct |
4 |
Correct |
1553 ms |
7900 KB |
Output is correct |
5 |
Correct |
1516 ms |
8068 KB |
Output is correct |
6 |
Correct |
2005 ms |
11460 KB |
Output is correct |
7 |
Correct |
2003 ms |
11340 KB |
Output is correct |
8 |
Correct |
1974 ms |
11556 KB |
Output is correct |
9 |
Correct |
180 ms |
4948 KB |
Output is correct |
10 |
Correct |
1495 ms |
8416 KB |
Output is correct |
11 |
Correct |
1450 ms |
8040 KB |
Output is correct |
12 |
Correct |
1260 ms |
9912 KB |
Output is correct |
13 |
Correct |
1159 ms |
9812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1226 ms |
4744 KB |
Output is correct |
2 |
Correct |
1088 ms |
6572 KB |
Output is correct |
3 |
Correct |
1477 ms |
7404 KB |
Output is correct |
4 |
Correct |
1226 ms |
7040 KB |
Output is correct |
5 |
Correct |
184 ms |
5008 KB |
Output is correct |
6 |
Correct |
1403 ms |
7208 KB |
Output is correct |
7 |
Correct |
1165 ms |
6892 KB |
Output is correct |
8 |
Correct |
964 ms |
6652 KB |
Output is correct |
9 |
Correct |
876 ms |
7196 KB |
Output is correct |
10 |
Correct |
732 ms |
6860 KB |
Output is correct |
11 |
Correct |
772 ms |
6608 KB |
Output is correct |
12 |
Correct |
636 ms |
6328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1428 ms |
5880 KB |
Output is correct |
2 |
Correct |
180 ms |
4944 KB |
Output is correct |
3 |
Correct |
137 ms |
6416 KB |
Output is correct |
4 |
Correct |
113 ms |
6480 KB |
Output is correct |
5 |
Correct |
1414 ms |
8056 KB |
Output is correct |
6 |
Correct |
1517 ms |
8476 KB |
Output is correct |
7 |
Correct |
1462 ms |
8324 KB |
Output is correct |
8 |
Correct |
787 ms |
6652 KB |
Output is correct |
9 |
Correct |
822 ms |
6644 KB |
Output is correct |
10 |
Correct |
896 ms |
9172 KB |
Output is correct |
11 |
Correct |
1144 ms |
8112 KB |
Output is correct |
12 |
Correct |
1096 ms |
8024 KB |
Output is correct |
13 |
Correct |
1181 ms |
10104 KB |
Output is correct |
14 |
Correct |
1240 ms |
9276 KB |
Output is correct |
15 |
Correct |
1289 ms |
8444 KB |
Output is correct |
16 |
Correct |
1381 ms |
8468 KB |
Output is correct |
17 |
Correct |
1435 ms |
8596 KB |
Output is correct |
18 |
Correct |
1383 ms |
8740 KB |
Output is correct |
19 |
Correct |
1387 ms |
8656 KB |
Output is correct |
20 |
Correct |
1295 ms |
10716 KB |
Output is correct |
21 |
Correct |
1273 ms |
10552 KB |
Output is correct |
22 |
Correct |
1377 ms |
10688 KB |
Output is correct |
23 |
Correct |
1342 ms |
9476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1504 ms |
5056 KB |
Output is correct |
2 |
Correct |
1465 ms |
8448 KB |
Output is correct |
3 |
Correct |
1472 ms |
7844 KB |
Output is correct |
4 |
Correct |
1553 ms |
7900 KB |
Output is correct |
5 |
Correct |
1516 ms |
8068 KB |
Output is correct |
6 |
Correct |
2005 ms |
11460 KB |
Output is correct |
7 |
Correct |
2003 ms |
11340 KB |
Output is correct |
8 |
Correct |
1974 ms |
11556 KB |
Output is correct |
9 |
Correct |
180 ms |
4948 KB |
Output is correct |
10 |
Correct |
1495 ms |
8416 KB |
Output is correct |
11 |
Correct |
1450 ms |
8040 KB |
Output is correct |
12 |
Correct |
1260 ms |
9912 KB |
Output is correct |
13 |
Correct |
1159 ms |
9812 KB |
Output is correct |
14 |
Correct |
1226 ms |
4744 KB |
Output is correct |
15 |
Correct |
1088 ms |
6572 KB |
Output is correct |
16 |
Correct |
1477 ms |
7404 KB |
Output is correct |
17 |
Correct |
1226 ms |
7040 KB |
Output is correct |
18 |
Correct |
184 ms |
5008 KB |
Output is correct |
19 |
Correct |
1403 ms |
7208 KB |
Output is correct |
20 |
Correct |
1165 ms |
6892 KB |
Output is correct |
21 |
Correct |
964 ms |
6652 KB |
Output is correct |
22 |
Correct |
876 ms |
7196 KB |
Output is correct |
23 |
Correct |
732 ms |
6860 KB |
Output is correct |
24 |
Correct |
772 ms |
6608 KB |
Output is correct |
25 |
Correct |
636 ms |
6328 KB |
Output is correct |
26 |
Correct |
1460 ms |
7372 KB |
Output is correct |
27 |
Correct |
1802 ms |
8240 KB |
Output is correct |
28 |
Correct |
1515 ms |
7336 KB |
Output is correct |
29 |
Correct |
1068 ms |
7072 KB |
Output is correct |
30 |
Correct |
1759 ms |
7948 KB |
Output is correct |
31 |
Correct |
1673 ms |
7852 KB |
Output is correct |
32 |
Correct |
1685 ms |
7800 KB |
Output is correct |
33 |
Correct |
1505 ms |
7624 KB |
Output is correct |
34 |
Correct |
1481 ms |
7448 KB |
Output is correct |
35 |
Correct |
1526 ms |
7552 KB |
Output is correct |
36 |
Correct |
1140 ms |
7240 KB |
Output is correct |
37 |
Correct |
1082 ms |
7228 KB |
Output is correct |
38 |
Correct |
1102 ms |
7132 KB |
Output is correct |
39 |
Correct |
897 ms |
6864 KB |
Output is correct |
40 |
Correct |
914 ms |
6928 KB |
Output is correct |
41 |
Correct |
884 ms |
6900 KB |
Output is correct |
42 |
Correct |
756 ms |
7116 KB |
Output is correct |
43 |
Correct |
765 ms |
7348 KB |
Output is correct |
44 |
Correct |
751 ms |
7504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
37 ms |
3528 KB |
Output is correct |
4 |
Correct |
18 ms |
2652 KB |
Output is correct |
5 |
Correct |
42 ms |
3672 KB |
Output is correct |
6 |
Correct |
31 ms |
3732 KB |
Output is correct |
7 |
Correct |
43 ms |
4252 KB |
Output is correct |
8 |
Correct |
49 ms |
3424 KB |
Output is correct |
9 |
Correct |
47 ms |
4688 KB |
Output is correct |
10 |
Correct |
49 ms |
3520 KB |
Output is correct |
11 |
Correct |
49 ms |
3496 KB |
Output is correct |
12 |
Correct |
61 ms |
4008 KB |
Output is correct |
13 |
Correct |
55 ms |
3416 KB |
Output is correct |
14 |
Correct |
53 ms |
3416 KB |
Output is correct |
15 |
Correct |
52 ms |
3604 KB |
Output is correct |
16 |
Correct |
43 ms |
4224 KB |
Output is correct |
17 |
Correct |
48 ms |
4008 KB |
Output is correct |
18 |
Correct |
1504 ms |
5056 KB |
Output is correct |
19 |
Correct |
1465 ms |
8448 KB |
Output is correct |
20 |
Correct |
1472 ms |
7844 KB |
Output is correct |
21 |
Correct |
1553 ms |
7900 KB |
Output is correct |
22 |
Correct |
1516 ms |
8068 KB |
Output is correct |
23 |
Correct |
2005 ms |
11460 KB |
Output is correct |
24 |
Correct |
2003 ms |
11340 KB |
Output is correct |
25 |
Correct |
1974 ms |
11556 KB |
Output is correct |
26 |
Correct |
180 ms |
4948 KB |
Output is correct |
27 |
Correct |
1495 ms |
8416 KB |
Output is correct |
28 |
Correct |
1450 ms |
8040 KB |
Output is correct |
29 |
Correct |
1260 ms |
9912 KB |
Output is correct |
30 |
Correct |
1159 ms |
9812 KB |
Output is correct |
31 |
Correct |
1226 ms |
4744 KB |
Output is correct |
32 |
Correct |
1088 ms |
6572 KB |
Output is correct |
33 |
Correct |
1477 ms |
7404 KB |
Output is correct |
34 |
Correct |
1226 ms |
7040 KB |
Output is correct |
35 |
Correct |
184 ms |
5008 KB |
Output is correct |
36 |
Correct |
1403 ms |
7208 KB |
Output is correct |
37 |
Correct |
1165 ms |
6892 KB |
Output is correct |
38 |
Correct |
964 ms |
6652 KB |
Output is correct |
39 |
Correct |
876 ms |
7196 KB |
Output is correct |
40 |
Correct |
732 ms |
6860 KB |
Output is correct |
41 |
Correct |
772 ms |
6608 KB |
Output is correct |
42 |
Correct |
636 ms |
6328 KB |
Output is correct |
43 |
Correct |
1428 ms |
5880 KB |
Output is correct |
44 |
Correct |
180 ms |
4944 KB |
Output is correct |
45 |
Correct |
137 ms |
6416 KB |
Output is correct |
46 |
Correct |
113 ms |
6480 KB |
Output is correct |
47 |
Correct |
1414 ms |
8056 KB |
Output is correct |
48 |
Correct |
1517 ms |
8476 KB |
Output is correct |
49 |
Correct |
1462 ms |
8324 KB |
Output is correct |
50 |
Correct |
787 ms |
6652 KB |
Output is correct |
51 |
Correct |
822 ms |
6644 KB |
Output is correct |
52 |
Correct |
896 ms |
9172 KB |
Output is correct |
53 |
Correct |
1144 ms |
8112 KB |
Output is correct |
54 |
Correct |
1096 ms |
8024 KB |
Output is correct |
55 |
Correct |
1181 ms |
10104 KB |
Output is correct |
56 |
Correct |
1240 ms |
9276 KB |
Output is correct |
57 |
Correct |
1289 ms |
8444 KB |
Output is correct |
58 |
Correct |
1381 ms |
8468 KB |
Output is correct |
59 |
Correct |
1435 ms |
8596 KB |
Output is correct |
60 |
Correct |
1383 ms |
8740 KB |
Output is correct |
61 |
Correct |
1387 ms |
8656 KB |
Output is correct |
62 |
Correct |
1295 ms |
10716 KB |
Output is correct |
63 |
Correct |
1273 ms |
10552 KB |
Output is correct |
64 |
Correct |
1377 ms |
10688 KB |
Output is correct |
65 |
Correct |
1342 ms |
9476 KB |
Output is correct |
66 |
Correct |
1460 ms |
7372 KB |
Output is correct |
67 |
Correct |
1802 ms |
8240 KB |
Output is correct |
68 |
Correct |
1515 ms |
7336 KB |
Output is correct |
69 |
Correct |
1068 ms |
7072 KB |
Output is correct |
70 |
Correct |
1759 ms |
7948 KB |
Output is correct |
71 |
Correct |
1673 ms |
7852 KB |
Output is correct |
72 |
Correct |
1685 ms |
7800 KB |
Output is correct |
73 |
Correct |
1505 ms |
7624 KB |
Output is correct |
74 |
Correct |
1481 ms |
7448 KB |
Output is correct |
75 |
Correct |
1526 ms |
7552 KB |
Output is correct |
76 |
Correct |
1140 ms |
7240 KB |
Output is correct |
77 |
Correct |
1082 ms |
7228 KB |
Output is correct |
78 |
Correct |
1102 ms |
7132 KB |
Output is correct |
79 |
Correct |
897 ms |
6864 KB |
Output is correct |
80 |
Correct |
914 ms |
6928 KB |
Output is correct |
81 |
Correct |
884 ms |
6900 KB |
Output is correct |
82 |
Correct |
756 ms |
7116 KB |
Output is correct |
83 |
Correct |
765 ms |
7348 KB |
Output is correct |
84 |
Correct |
751 ms |
7504 KB |
Output is correct |
85 |
Correct |
1706 ms |
9576 KB |
Output is correct |
86 |
Correct |
157 ms |
7108 KB |
Output is correct |
87 |
Correct |
112 ms |
8296 KB |
Output is correct |
88 |
Correct |
1603 ms |
9044 KB |
Output is correct |
89 |
Correct |
1758 ms |
9036 KB |
Output is correct |
90 |
Correct |
1672 ms |
9940 KB |
Output is correct |
91 |
Correct |
1518 ms |
7616 KB |
Output is correct |
92 |
Correct |
1524 ms |
7632 KB |
Output is correct |
93 |
Correct |
2102 ms |
10232 KB |
Output is correct |
94 |
Correct |
1471 ms |
8684 KB |
Output is correct |
95 |
Correct |
1565 ms |
8752 KB |
Output is correct |
96 |
Correct |
1491 ms |
11912 KB |
Output is correct |
97 |
Correct |
1474 ms |
8908 KB |
Output is correct |
98 |
Correct |
1394 ms |
8636 KB |
Output is correct |
99 |
Correct |
1729 ms |
9044 KB |
Output is correct |
100 |
Correct |
1700 ms |
9728 KB |
Output is correct |
101 |
Correct |
1789 ms |
9268 KB |
Output is correct |
102 |
Correct |
1783 ms |
9276 KB |
Output is correct |
103 |
Correct |
1586 ms |
12172 KB |
Output is correct |
104 |
Correct |
1597 ms |
12036 KB |
Output is correct |
105 |
Correct |
1281 ms |
10848 KB |
Output is correct |
106 |
Correct |
1118 ms |
10108 KB |
Output is correct |
107 |
Correct |
1390 ms |
10892 KB |
Output is correct |
108 |
Correct |
1642 ms |
11232 KB |
Output is correct |
109 |
Correct |
1567 ms |
11008 KB |
Output is correct |