# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
318754 |
2020-11-03T06:36:11 Z |
BeanZ |
Bridges (APIO19_bridges) |
C++14 |
|
2618 ms |
131676 KB |
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
const int N = 1e5 + 5;
vector<pair<ll, ll>> rb;
vector<ll> join[N];
ll u[N], v[N], d[N], t[N], a[N], b[N], ch[N], p[N], ans[N];
void rollback(ll u){
while (rb.size() > u){
p[rb.back().first] = rb.back().second;
rb.pop_back();
}
}
ll find_set(ll u){
if (p[u] < 0) return u;
return find_set(p[u]);
}
void dsu(ll u, ll v){
u = find_set(u);
v = find_set(v);
if (u == v) return;
if (p[u] > p[v]) swap(u, v);
rb.push_back({u, p[u]});
rb.push_back({v, p[v]});
p[u] += p[v];
p[v] = u;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("A.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> u[i] >> v[i] >> d[i];
}
ll q;
cin >> q;
for (int i = 1; i <= q; i++){
cin >> t[i] >> a[i] >> b[i];
}
const int base = 1000;
for (int l = 1; l <= q; l += base){
for (int i = 1; i <= n; i++) p[i] = -1;
ll r = min(l + base - 1, q);
for (int i = 1; i <= m; i++) ch[i] = 0;
rb.clear();
vector<ll> memupd, memres, un;
for (int i = l; i <= r; i++){
if (t[i] == 1) memupd.push_back(a[i]);
}
for (int i = l; i <= r; i++){
if (t[i] == 1){
d[a[i]] = b[i];
ch[a[i]] = 1;
} else {
for (auto j : memupd){
if (d[j] >= b[i]){
join[i].push_back(j);
}
}
memres.push_back(i);
}
}
for (int i = 1; i <= m; i++){
if (ch[i] == 0) un.push_back(i);
}
sort(un.begin(), un.end(), [&](ll g, ll h){return d[g] > d[h];});
sort(memres.begin(), memres.end(), [&](ll g, ll h){return b[g] > b[h];});
ll now = 0;
//for (auto j : memres) cout << j << " ";
//cout << endl;
for (auto j : memres){
while (now < un.size() && d[un[now]] >= b[j]){
dsu(u[un[now]], v[un[now]]);
//cout << u[un[now]] << " " << v[un[now]] << " " << now << " " << a[j] << " " << j << endl;
now++;
}
ll tmp = rb.size();
for (auto o : join[j]){
dsu(u[o], v[o]);
}
//cout << b[j] << endl;
//cout << j << endl;
ans[j] = -p[find_set(a[j])];
//cout << j << " " << ans[j] << endl;
rollback(tmp);
}
}
for (int i = 1; i <= q; i++){
if (t[i] == 2) cout << ans[i] << endl;
}
}
/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
1
2 1 5
*/
Compilation message
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:11:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
11 | while (rb.size() > u){
| ~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:79:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | while (now < un.size() && d[un[now]] >= b[j]){
| ~~~~^~~~~~~~~~~
bridges.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
34 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
35 | freopen("test.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
47 ms |
9572 KB |
Output is correct |
4 |
Correct |
6 ms |
2924 KB |
Output is correct |
5 |
Correct |
50 ms |
10340 KB |
Output is correct |
6 |
Correct |
40 ms |
10468 KB |
Output is correct |
7 |
Correct |
48 ms |
10596 KB |
Output is correct |
8 |
Correct |
48 ms |
8932 KB |
Output is correct |
9 |
Correct |
71 ms |
14820 KB |
Output is correct |
10 |
Correct |
51 ms |
9700 KB |
Output is correct |
11 |
Correct |
50 ms |
9720 KB |
Output is correct |
12 |
Correct |
62 ms |
12004 KB |
Output is correct |
13 |
Correct |
58 ms |
10212 KB |
Output is correct |
14 |
Correct |
53 ms |
9316 KB |
Output is correct |
15 |
Correct |
58 ms |
10084 KB |
Output is correct |
16 |
Correct |
61 ms |
13028 KB |
Output is correct |
17 |
Correct |
62 ms |
12136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1476 ms |
73872 KB |
Output is correct |
2 |
Correct |
1498 ms |
73748 KB |
Output is correct |
3 |
Correct |
1506 ms |
74028 KB |
Output is correct |
4 |
Correct |
1561 ms |
73432 KB |
Output is correct |
5 |
Correct |
1545 ms |
73960 KB |
Output is correct |
6 |
Correct |
2330 ms |
131676 KB |
Output is correct |
7 |
Correct |
2318 ms |
128228 KB |
Output is correct |
8 |
Correct |
2356 ms |
128004 KB |
Output is correct |
9 |
Correct |
42 ms |
4452 KB |
Output is correct |
10 |
Correct |
1401 ms |
99808 KB |
Output is correct |
11 |
Correct |
1292 ms |
99232 KB |
Output is correct |
12 |
Correct |
1302 ms |
53608 KB |
Output is correct |
13 |
Correct |
1308 ms |
46744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1193 ms |
73432 KB |
Output is correct |
2 |
Correct |
1055 ms |
98024 KB |
Output is correct |
3 |
Correct |
1509 ms |
101212 KB |
Output is correct |
4 |
Correct |
1197 ms |
72668 KB |
Output is correct |
5 |
Correct |
42 ms |
4452 KB |
Output is correct |
6 |
Correct |
1393 ms |
92640 KB |
Output is correct |
7 |
Correct |
1111 ms |
64860 KB |
Output is correct |
8 |
Correct |
946 ms |
49004 KB |
Output is correct |
9 |
Correct |
826 ms |
40840 KB |
Output is correct |
10 |
Correct |
717 ms |
29356 KB |
Output is correct |
11 |
Correct |
809 ms |
38296 KB |
Output is correct |
12 |
Correct |
696 ms |
28244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1726 ms |
8196 KB |
Output is correct |
2 |
Correct |
46 ms |
5988 KB |
Output is correct |
3 |
Correct |
176 ms |
7240 KB |
Output is correct |
4 |
Correct |
89 ms |
7376 KB |
Output is correct |
5 |
Correct |
899 ms |
10196 KB |
Output is correct |
6 |
Correct |
1679 ms |
10096 KB |
Output is correct |
7 |
Correct |
887 ms |
10124 KB |
Output is correct |
8 |
Correct |
776 ms |
9104 KB |
Output is correct |
9 |
Correct |
768 ms |
8984 KB |
Output is correct |
10 |
Correct |
772 ms |
8984 KB |
Output is correct |
11 |
Correct |
1259 ms |
9584 KB |
Output is correct |
12 |
Correct |
1241 ms |
9472 KB |
Output is correct |
13 |
Correct |
1288 ms |
9516 KB |
Output is correct |
14 |
Correct |
783 ms |
9816 KB |
Output is correct |
15 |
Correct |
847 ms |
9860 KB |
Output is correct |
16 |
Correct |
1704 ms |
10172 KB |
Output is correct |
17 |
Correct |
1712 ms |
10228 KB |
Output is correct |
18 |
Correct |
1692 ms |
10216 KB |
Output is correct |
19 |
Correct |
1704 ms |
10408 KB |
Output is correct |
20 |
Correct |
1446 ms |
10648 KB |
Output is correct |
21 |
Correct |
1431 ms |
10868 KB |
Output is correct |
22 |
Correct |
1663 ms |
11452 KB |
Output is correct |
23 |
Correct |
964 ms |
9536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1476 ms |
73872 KB |
Output is correct |
2 |
Correct |
1498 ms |
73748 KB |
Output is correct |
3 |
Correct |
1506 ms |
74028 KB |
Output is correct |
4 |
Correct |
1561 ms |
73432 KB |
Output is correct |
5 |
Correct |
1545 ms |
73960 KB |
Output is correct |
6 |
Correct |
2330 ms |
131676 KB |
Output is correct |
7 |
Correct |
2318 ms |
128228 KB |
Output is correct |
8 |
Correct |
2356 ms |
128004 KB |
Output is correct |
9 |
Correct |
42 ms |
4452 KB |
Output is correct |
10 |
Correct |
1401 ms |
99808 KB |
Output is correct |
11 |
Correct |
1292 ms |
99232 KB |
Output is correct |
12 |
Correct |
1302 ms |
53608 KB |
Output is correct |
13 |
Correct |
1308 ms |
46744 KB |
Output is correct |
14 |
Correct |
1193 ms |
73432 KB |
Output is correct |
15 |
Correct |
1055 ms |
98024 KB |
Output is correct |
16 |
Correct |
1509 ms |
101212 KB |
Output is correct |
17 |
Correct |
1197 ms |
72668 KB |
Output is correct |
18 |
Correct |
42 ms |
4452 KB |
Output is correct |
19 |
Correct |
1393 ms |
92640 KB |
Output is correct |
20 |
Correct |
1111 ms |
64860 KB |
Output is correct |
21 |
Correct |
946 ms |
49004 KB |
Output is correct |
22 |
Correct |
826 ms |
40840 KB |
Output is correct |
23 |
Correct |
717 ms |
29356 KB |
Output is correct |
24 |
Correct |
809 ms |
38296 KB |
Output is correct |
25 |
Correct |
696 ms |
28244 KB |
Output is correct |
26 |
Correct |
1490 ms |
73956 KB |
Output is correct |
27 |
Correct |
1931 ms |
103108 KB |
Output is correct |
28 |
Correct |
1564 ms |
72004 KB |
Output is correct |
29 |
Correct |
1082 ms |
29072 KB |
Output is correct |
30 |
Correct |
1794 ms |
89512 KB |
Output is correct |
31 |
Correct |
1822 ms |
91924 KB |
Output is correct |
32 |
Correct |
1838 ms |
92436 KB |
Output is correct |
33 |
Correct |
1523 ms |
72196 KB |
Output is correct |
34 |
Correct |
1523 ms |
72380 KB |
Output is correct |
35 |
Correct |
1530 ms |
72720 KB |
Output is correct |
36 |
Correct |
1136 ms |
35988 KB |
Output is correct |
37 |
Correct |
1125 ms |
34836 KB |
Output is correct |
38 |
Correct |
1096 ms |
33168 KB |
Output is correct |
39 |
Correct |
910 ms |
19344 KB |
Output is correct |
40 |
Correct |
910 ms |
18396 KB |
Output is correct |
41 |
Correct |
897 ms |
17792 KB |
Output is correct |
42 |
Correct |
878 ms |
17692 KB |
Output is correct |
43 |
Correct |
877 ms |
16880 KB |
Output is correct |
44 |
Correct |
871 ms |
16332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
47 ms |
9572 KB |
Output is correct |
4 |
Correct |
6 ms |
2924 KB |
Output is correct |
5 |
Correct |
50 ms |
10340 KB |
Output is correct |
6 |
Correct |
40 ms |
10468 KB |
Output is correct |
7 |
Correct |
48 ms |
10596 KB |
Output is correct |
8 |
Correct |
48 ms |
8932 KB |
Output is correct |
9 |
Correct |
71 ms |
14820 KB |
Output is correct |
10 |
Correct |
51 ms |
9700 KB |
Output is correct |
11 |
Correct |
50 ms |
9720 KB |
Output is correct |
12 |
Correct |
62 ms |
12004 KB |
Output is correct |
13 |
Correct |
58 ms |
10212 KB |
Output is correct |
14 |
Correct |
53 ms |
9316 KB |
Output is correct |
15 |
Correct |
58 ms |
10084 KB |
Output is correct |
16 |
Correct |
61 ms |
13028 KB |
Output is correct |
17 |
Correct |
62 ms |
12136 KB |
Output is correct |
18 |
Correct |
1476 ms |
73872 KB |
Output is correct |
19 |
Correct |
1498 ms |
73748 KB |
Output is correct |
20 |
Correct |
1506 ms |
74028 KB |
Output is correct |
21 |
Correct |
1561 ms |
73432 KB |
Output is correct |
22 |
Correct |
1545 ms |
73960 KB |
Output is correct |
23 |
Correct |
2330 ms |
131676 KB |
Output is correct |
24 |
Correct |
2318 ms |
128228 KB |
Output is correct |
25 |
Correct |
2356 ms |
128004 KB |
Output is correct |
26 |
Correct |
42 ms |
4452 KB |
Output is correct |
27 |
Correct |
1401 ms |
99808 KB |
Output is correct |
28 |
Correct |
1292 ms |
99232 KB |
Output is correct |
29 |
Correct |
1302 ms |
53608 KB |
Output is correct |
30 |
Correct |
1308 ms |
46744 KB |
Output is correct |
31 |
Correct |
1193 ms |
73432 KB |
Output is correct |
32 |
Correct |
1055 ms |
98024 KB |
Output is correct |
33 |
Correct |
1509 ms |
101212 KB |
Output is correct |
34 |
Correct |
1197 ms |
72668 KB |
Output is correct |
35 |
Correct |
42 ms |
4452 KB |
Output is correct |
36 |
Correct |
1393 ms |
92640 KB |
Output is correct |
37 |
Correct |
1111 ms |
64860 KB |
Output is correct |
38 |
Correct |
946 ms |
49004 KB |
Output is correct |
39 |
Correct |
826 ms |
40840 KB |
Output is correct |
40 |
Correct |
717 ms |
29356 KB |
Output is correct |
41 |
Correct |
809 ms |
38296 KB |
Output is correct |
42 |
Correct |
696 ms |
28244 KB |
Output is correct |
43 |
Correct |
1726 ms |
8196 KB |
Output is correct |
44 |
Correct |
46 ms |
5988 KB |
Output is correct |
45 |
Correct |
176 ms |
7240 KB |
Output is correct |
46 |
Correct |
89 ms |
7376 KB |
Output is correct |
47 |
Correct |
899 ms |
10196 KB |
Output is correct |
48 |
Correct |
1679 ms |
10096 KB |
Output is correct |
49 |
Correct |
887 ms |
10124 KB |
Output is correct |
50 |
Correct |
776 ms |
9104 KB |
Output is correct |
51 |
Correct |
768 ms |
8984 KB |
Output is correct |
52 |
Correct |
772 ms |
8984 KB |
Output is correct |
53 |
Correct |
1259 ms |
9584 KB |
Output is correct |
54 |
Correct |
1241 ms |
9472 KB |
Output is correct |
55 |
Correct |
1288 ms |
9516 KB |
Output is correct |
56 |
Correct |
783 ms |
9816 KB |
Output is correct |
57 |
Correct |
847 ms |
9860 KB |
Output is correct |
58 |
Correct |
1704 ms |
10172 KB |
Output is correct |
59 |
Correct |
1712 ms |
10228 KB |
Output is correct |
60 |
Correct |
1692 ms |
10216 KB |
Output is correct |
61 |
Correct |
1704 ms |
10408 KB |
Output is correct |
62 |
Correct |
1446 ms |
10648 KB |
Output is correct |
63 |
Correct |
1431 ms |
10868 KB |
Output is correct |
64 |
Correct |
1663 ms |
11452 KB |
Output is correct |
65 |
Correct |
964 ms |
9536 KB |
Output is correct |
66 |
Correct |
1490 ms |
73956 KB |
Output is correct |
67 |
Correct |
1931 ms |
103108 KB |
Output is correct |
68 |
Correct |
1564 ms |
72004 KB |
Output is correct |
69 |
Correct |
1082 ms |
29072 KB |
Output is correct |
70 |
Correct |
1794 ms |
89512 KB |
Output is correct |
71 |
Correct |
1822 ms |
91924 KB |
Output is correct |
72 |
Correct |
1838 ms |
92436 KB |
Output is correct |
73 |
Correct |
1523 ms |
72196 KB |
Output is correct |
74 |
Correct |
1523 ms |
72380 KB |
Output is correct |
75 |
Correct |
1530 ms |
72720 KB |
Output is correct |
76 |
Correct |
1136 ms |
35988 KB |
Output is correct |
77 |
Correct |
1125 ms |
34836 KB |
Output is correct |
78 |
Correct |
1096 ms |
33168 KB |
Output is correct |
79 |
Correct |
910 ms |
19344 KB |
Output is correct |
80 |
Correct |
910 ms |
18396 KB |
Output is correct |
81 |
Correct |
897 ms |
17792 KB |
Output is correct |
82 |
Correct |
878 ms |
17692 KB |
Output is correct |
83 |
Correct |
877 ms |
16880 KB |
Output is correct |
84 |
Correct |
871 ms |
16332 KB |
Output is correct |
85 |
Correct |
2317 ms |
78848 KB |
Output is correct |
86 |
Correct |
223 ms |
13980 KB |
Output is correct |
87 |
Correct |
151 ms |
18336 KB |
Output is correct |
88 |
Correct |
1482 ms |
90628 KB |
Output is correct |
89 |
Correct |
2324 ms |
77352 KB |
Output is correct |
90 |
Correct |
1492 ms |
99520 KB |
Output is correct |
91 |
Correct |
1573 ms |
76444 KB |
Output is correct |
92 |
Correct |
1576 ms |
76256 KB |
Output is correct |
93 |
Correct |
2344 ms |
114196 KB |
Output is correct |
94 |
Correct |
1945 ms |
77792 KB |
Output is correct |
95 |
Correct |
1933 ms |
77492 KB |
Output is correct |
96 |
Correct |
2389 ms |
118160 KB |
Output is correct |
97 |
Correct |
1122 ms |
43340 KB |
Output is correct |
98 |
Correct |
1145 ms |
40416 KB |
Output is correct |
99 |
Correct |
2342 ms |
79980 KB |
Output is correct |
100 |
Correct |
2333 ms |
78740 KB |
Output is correct |
101 |
Correct |
2404 ms |
78568 KB |
Output is correct |
102 |
Correct |
2343 ms |
78740 KB |
Output is correct |
103 |
Correct |
2618 ms |
123932 KB |
Output is correct |
104 |
Correct |
2608 ms |
123376 KB |
Output is correct |
105 |
Correct |
1863 ms |
51292 KB |
Output is correct |
106 |
Correct |
1471 ms |
30976 KB |
Output is correct |
107 |
Correct |
1804 ms |
57532 KB |
Output is correct |
108 |
Correct |
2444 ms |
114060 KB |
Output is correct |
109 |
Correct |
1830 ms |
117352 KB |
Output is correct |