# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
258039 | 2020-08-05T08:43:27 Z | BamiTorabi | Bridges (APIO19_bridges) | C++14 | 2103 ms | 14324 KB |
//Sasayego! Sasayego! Shinzou wo Sasageyo! #include <iostream> #include <iomanip> #include <algorithm> #include <cmath> #include <ctime> #include <cstring> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <deque> #include <numeric> #include <bitset> #include <ctime> #define debug(x) cerr << #x << " = " << x << endl #define lid (id << 1) #define rid (lid ^ 1) using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll, ll> pll; typedef pair <int, int> pii; const int maxN = 1e5 + 5; const int SQ = 1000; const ll INF = 1e18; const ll MOD = 1e9 + 7; struct triple{ int first, second, third; } E[maxN], Q[maxN]; stack <int> st; int par[maxN], sz[maxN]; int change[maxN], wt[maxN], ans[maxN]; vector <int> vec, Eix[maxN], Qix[maxN], tmp; int getpar(int v, bool flag = false){ if (!flag) return (par[v] == v ? v : par[v] = getpar(par[v], flag)); while (par[v] != v) v = par[v]; return v; } void join(int u, int v, bool flag = false){ u = getpar(u, flag); v = getpar(v, flag); if (u == v){ if (flag) st.push(-1); return; } if (sz[u] < sz[v]) swap(u, v); if (flag) st.push(v); par[v] = u; sz[u] += sz[v]; return; } void undo(){ int v = st.top(); st.pop(); if (v == -1) return; int u = par[v]; par[v] = v; sz[u] -= sz[v]; return; } int main(){ time_t START = clock(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d%d%d", &E[i].second, &E[i].third, &E[i].first); int q; scanf("%d", &q); for (int i = 0; i < q; i++){ scanf("%d%d%d", &Q[i].first, &Q[i].second, &Q[i].third); if (Q[i].first == 2) vec.push_back(Q[i].third); } sort(vec.begin(), vec.end()); vec.resize(unique(vec.begin(), vec.end()) - vec.begin()); for (int i = 1; i <= m; i++) E[i].first = upper_bound(vec.begin(), vec.end(), E[i].first) - vec.begin() - 1; for (int i = 0; i < q; i++) Q[i].third = upper_bound(vec.begin(), vec.end(), Q[i].third) - vec.begin() - 1; for (int id = 0, ss = SQ; id < q; id += ss){ ss = min(ss, q - id); for (int i = 1; i <= m; i++) change[i] = false; for (int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; } for (int i = id; i < id + ss; i++){ if (Q[i].first == 1) change[Q[i].second] = true; else Qix[Q[i].third].push_back(i); } for (int i = 1; i <= m; i++) (change[i] ? tmp.push_back(i) : Eix[E[i].first].push_back(i)); sort(tmp.begin(), tmp.end()); for (int i = (int)vec.size(); i > -1; i--){ for (int e : Eix[i]) join(E[e].second, E[e].third); for (int x : Qix[i]){ for (int e : tmp) wt[e] = E[e].first; for (int j = id; j < x; j++) if (Q[j].first == 1) wt[Q[j].second] = Q[j].third; for (int e : tmp) if (wt[e] >= i) join(E[e].second, E[e].third, 1); ans[x] = sz[getpar(Q[x].second, 1)]; while (!st.empty()) undo(); } Eix[i].clear(); Qix[i].clear(); } for (int i = id; i < id + ss; i++){ if (Q[i].first == 1) E[Q[i].second].first = Q[i].third; else printf("%d\n", ans[i]); } tmp.clear(); } time_t FINISH = clock(); cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " mill.seconds.\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 5120 KB | Output is correct |
2 | Correct | 3 ms | 5120 KB | Output is correct |
3 | Correct | 41 ms | 5496 KB | Output is correct |
4 | Correct | 15 ms | 5632 KB | Output is correct |
5 | Correct | 24 ms | 5376 KB | Output is correct |
6 | Correct | 19 ms | 5248 KB | Output is correct |
7 | Correct | 22 ms | 5248 KB | Output is correct |
8 | Correct | 23 ms | 5368 KB | Output is correct |
9 | Correct | 25 ms | 5376 KB | Output is correct |
10 | Correct | 23 ms | 5376 KB | Output is correct |
11 | Correct | 24 ms | 5496 KB | Output is correct |
12 | Correct | 24 ms | 5376 KB | Output is correct |
13 | Correct | 29 ms | 5376 KB | Output is correct |
14 | Correct | 28 ms | 5376 KB | Output is correct |
15 | Correct | 27 ms | 5376 KB | Output is correct |
16 | Correct | 21 ms | 5248 KB | Output is correct |
17 | Correct | 22 ms | 5248 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1427 ms | 11128 KB | Output is correct |
2 | Correct | 1482 ms | 11088 KB | Output is correct |
3 | Correct | 1512 ms | 11000 KB | Output is correct |
4 | Correct | 1344 ms | 11012 KB | Output is correct |
5 | Correct | 1414 ms | 11128 KB | Output is correct |
6 | Correct | 1309 ms | 9596 KB | Output is correct |
7 | Correct | 1321 ms | 10080 KB | Output is correct |
8 | Correct | 1449 ms | 10108 KB | Output is correct |
9 | Correct | 168 ms | 10356 KB | Output is correct |
10 | Correct | 1156 ms | 8952 KB | Output is correct |
11 | Correct | 1077 ms | 8808 KB | Output is correct |
12 | Correct | 698 ms | 11336 KB | Output is correct |
13 | Correct | 604 ms | 8692 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1178 ms | 10392 KB | Output is correct |
2 | Correct | 864 ms | 8608 KB | Output is correct |
3 | Correct | 1285 ms | 9548 KB | Output is correct |
4 | Correct | 1234 ms | 10488 KB | Output is correct |
5 | Correct | 168 ms | 10400 KB | Output is correct |
6 | Correct | 1225 ms | 10456 KB | Output is correct |
7 | Correct | 1116 ms | 10488 KB | Output is correct |
8 | Correct | 951 ms | 10360 KB | Output is correct |
9 | Correct | 720 ms | 11896 KB | Output is correct |
10 | Correct | 700 ms | 11892 KB | Output is correct |
11 | Correct | 562 ms | 8312 KB | Output is correct |
12 | Correct | 515 ms | 8360 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1412 ms | 14324 KB | Output is correct |
2 | Correct | 158 ms | 10484 KB | Output is correct |
3 | Correct | 119 ms | 7844 KB | Output is correct |
4 | Correct | 75 ms | 7412 KB | Output is correct |
5 | Correct | 589 ms | 10252 KB | Output is correct |
6 | Correct | 1374 ms | 14192 KB | Output is correct |
7 | Correct | 580 ms | 10100 KB | Output is correct |
8 | Correct | 912 ms | 12528 KB | Output is correct |
9 | Correct | 895 ms | 12724 KB | Output is correct |
10 | Correct | 487 ms | 12020 KB | Output is correct |
11 | Correct | 1258 ms | 13456 KB | Output is correct |
12 | Correct | 1482 ms | 13412 KB | Output is correct |
13 | Correct | 642 ms | 12784 KB | Output is correct |
14 | Correct | 547 ms | 10420 KB | Output is correct |
15 | Correct | 559 ms | 10484 KB | Output is correct |
16 | Correct | 1481 ms | 14192 KB | Output is correct |
17 | Correct | 1830 ms | 14176 KB | Output is correct |
18 | Correct | 1797 ms | 14204 KB | Output is correct |
19 | Correct | 1654 ms | 14068 KB | Output is correct |
20 | Correct | 736 ms | 12712 KB | Output is correct |
21 | Correct | 679 ms | 12968 KB | Output is correct |
22 | Correct | 996 ms | 13632 KB | Output is correct |
23 | Correct | 531 ms | 9824 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1427 ms | 11128 KB | Output is correct |
2 | Correct | 1482 ms | 11088 KB | Output is correct |
3 | Correct | 1512 ms | 11000 KB | Output is correct |
4 | Correct | 1344 ms | 11012 KB | Output is correct |
5 | Correct | 1414 ms | 11128 KB | Output is correct |
6 | Correct | 1309 ms | 9596 KB | Output is correct |
7 | Correct | 1321 ms | 10080 KB | Output is correct |
8 | Correct | 1449 ms | 10108 KB | Output is correct |
9 | Correct | 168 ms | 10356 KB | Output is correct |
10 | Correct | 1156 ms | 8952 KB | Output is correct |
11 | Correct | 1077 ms | 8808 KB | Output is correct |
12 | Correct | 698 ms | 11336 KB | Output is correct |
13 | Correct | 604 ms | 8692 KB | Output is correct |
14 | Correct | 1178 ms | 10392 KB | Output is correct |
15 | Correct | 864 ms | 8608 KB | Output is correct |
16 | Correct | 1285 ms | 9548 KB | Output is correct |
17 | Correct | 1234 ms | 10488 KB | Output is correct |
18 | Correct | 168 ms | 10400 KB | Output is correct |
19 | Correct | 1225 ms | 10456 KB | Output is correct |
20 | Correct | 1116 ms | 10488 KB | Output is correct |
21 | Correct | 951 ms | 10360 KB | Output is correct |
22 | Correct | 720 ms | 11896 KB | Output is correct |
23 | Correct | 700 ms | 11892 KB | Output is correct |
24 | Correct | 562 ms | 8312 KB | Output is correct |
25 | Correct | 515 ms | 8360 KB | Output is correct |
26 | Correct | 1472 ms | 11056 KB | Output is correct |
27 | Correct | 1664 ms | 9952 KB | Output is correct |
28 | Correct | 1460 ms | 11256 KB | Output is correct |
29 | Correct | 971 ms | 10616 KB | Output is correct |
30 | Correct | 1675 ms | 10516 KB | Output is correct |
31 | Correct | 1637 ms | 10416 KB | Output is correct |
32 | Correct | 1764 ms | 10360 KB | Output is correct |
33 | Correct | 1603 ms | 11000 KB | Output is correct |
34 | Correct | 1593 ms | 11128 KB | Output is correct |
35 | Correct | 1580 ms | 11000 KB | Output is correct |
36 | Correct | 1135 ms | 10824 KB | Output is correct |
37 | Correct | 1051 ms | 10744 KB | Output is correct |
38 | Correct | 1031 ms | 10744 KB | Output is correct |
39 | Correct | 1022 ms | 12476 KB | Output is correct |
40 | Correct | 860 ms | 12264 KB | Output is correct |
41 | Correct | 888 ms | 12276 KB | Output is correct |
42 | Correct | 631 ms | 8956 KB | Output is correct |
43 | Correct | 618 ms | 8952 KB | Output is correct |
44 | Correct | 614 ms | 8952 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 5120 KB | Output is correct |
2 | Correct | 3 ms | 5120 KB | Output is correct |
3 | Correct | 41 ms | 5496 KB | Output is correct |
4 | Correct | 15 ms | 5632 KB | Output is correct |
5 | Correct | 24 ms | 5376 KB | Output is correct |
6 | Correct | 19 ms | 5248 KB | Output is correct |
7 | Correct | 22 ms | 5248 KB | Output is correct |
8 | Correct | 23 ms | 5368 KB | Output is correct |
9 | Correct | 25 ms | 5376 KB | Output is correct |
10 | Correct | 23 ms | 5376 KB | Output is correct |
11 | Correct | 24 ms | 5496 KB | Output is correct |
12 | Correct | 24 ms | 5376 KB | Output is correct |
13 | Correct | 29 ms | 5376 KB | Output is correct |
14 | Correct | 28 ms | 5376 KB | Output is correct |
15 | Correct | 27 ms | 5376 KB | Output is correct |
16 | Correct | 21 ms | 5248 KB | Output is correct |
17 | Correct | 22 ms | 5248 KB | Output is correct |
18 | Correct | 1427 ms | 11128 KB | Output is correct |
19 | Correct | 1482 ms | 11088 KB | Output is correct |
20 | Correct | 1512 ms | 11000 KB | Output is correct |
21 | Correct | 1344 ms | 11012 KB | Output is correct |
22 | Correct | 1414 ms | 11128 KB | Output is correct |
23 | Correct | 1309 ms | 9596 KB | Output is correct |
24 | Correct | 1321 ms | 10080 KB | Output is correct |
25 | Correct | 1449 ms | 10108 KB | Output is correct |
26 | Correct | 168 ms | 10356 KB | Output is correct |
27 | Correct | 1156 ms | 8952 KB | Output is correct |
28 | Correct | 1077 ms | 8808 KB | Output is correct |
29 | Correct | 698 ms | 11336 KB | Output is correct |
30 | Correct | 604 ms | 8692 KB | Output is correct |
31 | Correct | 1178 ms | 10392 KB | Output is correct |
32 | Correct | 864 ms | 8608 KB | Output is correct |
33 | Correct | 1285 ms | 9548 KB | Output is correct |
34 | Correct | 1234 ms | 10488 KB | Output is correct |
35 | Correct | 168 ms | 10400 KB | Output is correct |
36 | Correct | 1225 ms | 10456 KB | Output is correct |
37 | Correct | 1116 ms | 10488 KB | Output is correct |
38 | Correct | 951 ms | 10360 KB | Output is correct |
39 | Correct | 720 ms | 11896 KB | Output is correct |
40 | Correct | 700 ms | 11892 KB | Output is correct |
41 | Correct | 562 ms | 8312 KB | Output is correct |
42 | Correct | 515 ms | 8360 KB | Output is correct |
43 | Correct | 1412 ms | 14324 KB | Output is correct |
44 | Correct | 158 ms | 10484 KB | Output is correct |
45 | Correct | 119 ms | 7844 KB | Output is correct |
46 | Correct | 75 ms | 7412 KB | Output is correct |
47 | Correct | 589 ms | 10252 KB | Output is correct |
48 | Correct | 1374 ms | 14192 KB | Output is correct |
49 | Correct | 580 ms | 10100 KB | Output is correct |
50 | Correct | 912 ms | 12528 KB | Output is correct |
51 | Correct | 895 ms | 12724 KB | Output is correct |
52 | Correct | 487 ms | 12020 KB | Output is correct |
53 | Correct | 1258 ms | 13456 KB | Output is correct |
54 | Correct | 1482 ms | 13412 KB | Output is correct |
55 | Correct | 642 ms | 12784 KB | Output is correct |
56 | Correct | 547 ms | 10420 KB | Output is correct |
57 | Correct | 559 ms | 10484 KB | Output is correct |
58 | Correct | 1481 ms | 14192 KB | Output is correct |
59 | Correct | 1830 ms | 14176 KB | Output is correct |
60 | Correct | 1797 ms | 14204 KB | Output is correct |
61 | Correct | 1654 ms | 14068 KB | Output is correct |
62 | Correct | 736 ms | 12712 KB | Output is correct |
63 | Correct | 679 ms | 12968 KB | Output is correct |
64 | Correct | 996 ms | 13632 KB | Output is correct |
65 | Correct | 531 ms | 9824 KB | Output is correct |
66 | Correct | 1472 ms | 11056 KB | Output is correct |
67 | Correct | 1664 ms | 9952 KB | Output is correct |
68 | Correct | 1460 ms | 11256 KB | Output is correct |
69 | Correct | 971 ms | 10616 KB | Output is correct |
70 | Correct | 1675 ms | 10516 KB | Output is correct |
71 | Correct | 1637 ms | 10416 KB | Output is correct |
72 | Correct | 1764 ms | 10360 KB | Output is correct |
73 | Correct | 1603 ms | 11000 KB | Output is correct |
74 | Correct | 1593 ms | 11128 KB | Output is correct |
75 | Correct | 1580 ms | 11000 KB | Output is correct |
76 | Correct | 1135 ms | 10824 KB | Output is correct |
77 | Correct | 1051 ms | 10744 KB | Output is correct |
78 | Correct | 1031 ms | 10744 KB | Output is correct |
79 | Correct | 1022 ms | 12476 KB | Output is correct |
80 | Correct | 860 ms | 12264 KB | Output is correct |
81 | Correct | 888 ms | 12276 KB | Output is correct |
82 | Correct | 631 ms | 8956 KB | Output is correct |
83 | Correct | 618 ms | 8952 KB | Output is correct |
84 | Correct | 614 ms | 8952 KB | Output is correct |
85 | Correct | 1690 ms | 12476 KB | Output is correct |
86 | Correct | 155 ms | 8056 KB | Output is correct |
87 | Correct | 121 ms | 7792 KB | Output is correct |
88 | Correct | 1090 ms | 10244 KB | Output is correct |
89 | Correct | 1696 ms | 12388 KB | Output is correct |
90 | Correct | 1053 ms | 9864 KB | Output is correct |
91 | Correct | 1509 ms | 11096 KB | Output is correct |
92 | Correct | 1558 ms | 10988 KB | Output is correct |
93 | Correct | 1913 ms | 10312 KB | Output is correct |
94 | Correct | 1741 ms | 11652 KB | Output is correct |
95 | Correct | 1757 ms | 11684 KB | Output is correct |
96 | Correct | 1444 ms | 10908 KB | Output is correct |
97 | Correct | 743 ms | 10356 KB | Output is correct |
98 | Correct | 742 ms | 9592 KB | Output is correct |
99 | Correct | 2103 ms | 12380 KB | Output is correct |
100 | Correct | 1831 ms | 12632 KB | Output is correct |
101 | Correct | 2036 ms | 12296 KB | Output is correct |
102 | Correct | 2009 ms | 12364 KB | Output is correct |
103 | Correct | 1361 ms | 10912 KB | Output is correct |
104 | Correct | 1440 ms | 11076 KB | Output is correct |
105 | Correct | 832 ms | 9392 KB | Output is correct |
106 | Correct | 674 ms | 8940 KB | Output is correct |
107 | Correct | 928 ms | 12664 KB | Output is correct |
108 | Correct | 1499 ms | 11912 KB | Output is correct |
109 | Correct | 1157 ms | 9336 KB | Output is correct |