# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
209039 | 2020-03-13T01:56:02 Z | jtnydv25 | Bridges (APIO19_bridges) | C++14 | 2992 ms | 11532 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define sd(x) scanf("%d", &(x)) #define pii pair<int, int> #define F first #define S second #define all(c) ((c).begin()), ((c).end()) #define sz(x) ((int)(x).size()) #define ld long double template<class T,class U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os<<"("<<p.first<<", "<<p.second<<")"; return os; } template<class T> ostream& operator <<(ostream& os,const vector<T>& v){ os<<"{"; for(int i = 0;i < (int)v.size(); i++){ if(i)os<<", "; os<<v[i]; } os<<"}"; return os; } #ifdef LOCAL #define cerr cout #else #endif #define TRACE #ifdef TRACE #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void __f(const char* name, Arg1&& arg1){ cerr << name << " : " << arg1 << std::endl; } template <typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); } #else #define trace(...) #endif const int MASK = (1 << 30) - 1; struct rollback_array{ stack<ll> changes; vector<int> arr; int n; rollback_array(){n = 0;} rollback_array(int n) : n(n), arr(n){}; void setall(int x){ for(int i = 0; i < n; i++) arr[i] = x; } // if not to be rolled back just do arr[x] = v int & operator [] (int x){ return arr[x];} inline void update(int i, int v){ changes.push((((ll)i) << 30) + arr[i]); arr[i] = v; } inline void click(){ changes.push(-1); } inline void roll_back(){ while(!changes.empty()){ ll it = changes.top(); changes.pop(); if(it == -1) return; arr[it >> 30] = it & MASK; } } }; struct rollback_dsu{ int n; rollback_array par, num; rollback_dsu(int n) : n(n), par(n), num(n){ par.setall(n); num.setall(1); } int root(int x){ if(par[x] == n) return x; int rt = root(par[x]); par.update(x, rt); return rt; } void merge(int x, int y){ x = root(x); y = root(y); if(x == y) return; if(num[x] > num[y]) swap(x, y); par.update(x, y); num.update(y, num[x] + num[y]); } void click(){ par.click(); num.click(); } void roll_back(){ par.roll_back(); num.roll_back(); } }; const int N = 100005; int a[N], b[N], w[2 * N]; int type[N], s[N]; bitset<N> changing; const int BLOCK = 455; int ans[N]; int temp[2 * N]; int cntr = 0; int arr[N], sz_arr; void go(vector<int> & b){ int szb = sz(b); int pos_a = 0, pos_b = 0; cntr = 0; while(pos_a < sz_arr || pos_b < szb){ if(pos_a < sz_arr && (pos_b == szb || w[arr[pos_a]] >= w[b[pos_b]])){ temp[cntr++] = arr[pos_a++]; } else{ temp[cntr++] = b[pos_b++]; } } } int which[BLOCK][BLOCK]; // bitset<BLOCK> which[BLOCK]; int main(){ int n = 50000, m = 100000; sd(n); sd(m); for(int i = 0; i < m; i++){ // a[i] = rand() % n + 1; b[i] = rand() % n + 1; w[i] = rand() % 1000000; sd(a[i]); sd(b[i]); sd(w[i]); a[i]--; b[i]--; } int q = 100000; sd(q); for(int i = 0; i < q; i++){ // type[i] = rand() % 2 + 1; // if(type[i]==1) s[i] = rand() % m + 1; // else s[i] = rand() % n + 1; // w[i + m] = rand() % 1000000; sd(type[i]); sd(s[i]); sd(w[i + m]); s[i]--; } vector<int> perm(m); iota(all(perm), 0); sort(all(perm), [&](int i, int j){return w[i] > w[j];}); rollback_dsu D(n); for(int i = 0; i * BLOCK < q; i++){ int st = i * BLOCK, en = min(q - 1, st + BLOCK - 1); vector<int> queries; vector<int> changing_edges; changing.reset(); for(int j = st; j <= en; j++){ if(type[j] == 1){ changing[s[j]] = 1; } else{ queries.push_back(j + m); } } sz_arr = 0; for(int j = 0; j < m; j++){ int ind = perm[j]; if(changing[ind]){ changing_edges.push_back(ind); } else{ arr[sz_arr++] = ind; } } sort(all(queries), [&](int p, int q){return w[p] > w[q];}); go(queries); D.click(); for(int j = st; j <= en; j++){ if(type[j] == 1){ w[s[j]] = w[j + m]; }else{ for(int k = 0; k < sz(changing_edges); k++) which[j - st][k] = w[changing_edges[k]] >= w[j + m]; } } for(int j = 0; j < cntr; j++){ int ind = temp[j]; if(ind < m){ if(!changing[ind]){ D.merge(a[ind], b[ind]); } } else{ ind -= m; D.click(); for(int k = 0; k < sz(changing_edges); k++) if(which[ind - st][k]){ int e = changing_edges[k]; D.merge(a[e], b[e]); } ans[ind] = D.num[D.root(s[ind])]; D.roll_back(); } } D.roll_back(); sort(all(changing_edges), [&](int p, int q){return w[p] > w[q];}); go(changing_edges); for(int j = 0; j < m; j++) perm[j] = temp[j]; } for(int i = 0; i < q; i++) if(type[i] == 2) printf("%d\n", ans[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 34 ms | 1400 KB | Output is correct |
4 | Correct | 10 ms | 504 KB | Output is correct |
5 | Correct | 22 ms | 1400 KB | Output is correct |
6 | Correct | 18 ms | 1272 KB | Output is correct |
7 | Correct | 22 ms | 1368 KB | Output is correct |
8 | Correct | 21 ms | 1272 KB | Output is correct |
9 | Correct | 32 ms | 1404 KB | Output is correct |
10 | Correct | 23 ms | 1272 KB | Output is correct |
11 | Correct | 21 ms | 1272 KB | Output is correct |
12 | Correct | 24 ms | 1272 KB | Output is correct |
13 | Correct | 28 ms | 1400 KB | Output is correct |
14 | Correct | 25 ms | 1400 KB | Output is correct |
15 | Correct | 25 ms | 1400 KB | Output is correct |
16 | Correct | 26 ms | 1400 KB | Output is correct |
17 | Correct | 26 ms | 1384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1480 ms | 5724 KB | Output is correct |
2 | Correct | 1547 ms | 5688 KB | Output is correct |
3 | Correct | 1531 ms | 5724 KB | Output is correct |
4 | Correct | 1693 ms | 5648 KB | Output is correct |
5 | Correct | 1705 ms | 5760 KB | Output is correct |
6 | Correct | 2868 ms | 5736 KB | Output is correct |
7 | Correct | 2846 ms | 5840 KB | Output is correct |
8 | Correct | 2827 ms | 5688 KB | Output is correct |
9 | Correct | 61 ms | 2172 KB | Output is correct |
10 | Correct | 1969 ms | 5612 KB | Output is correct |
11 | Correct | 1749 ms | 5596 KB | Output is correct |
12 | Correct | 1749 ms | 5672 KB | Output is correct |
13 | Correct | 1645 ms | 5624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1178 ms | 4776 KB | Output is correct |
2 | Correct | 838 ms | 3460 KB | Output is correct |
3 | Correct | 1401 ms | 5032 KB | Output is correct |
4 | Correct | 1176 ms | 4784 KB | Output is correct |
5 | Correct | 60 ms | 2168 KB | Output is correct |
6 | Correct | 1297 ms | 4860 KB | Output is correct |
7 | Correct | 1075 ms | 4752 KB | Output is correct |
8 | Correct | 982 ms | 4868 KB | Output is correct |
9 | Correct | 893 ms | 5184 KB | Output is correct |
10 | Correct | 831 ms | 5012 KB | Output is correct |
11 | Correct | 924 ms | 4796 KB | Output is correct |
12 | Correct | 811 ms | 4756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1958 ms | 7552 KB | Output is correct |
2 | Correct | 70 ms | 2168 KB | Output is correct |
3 | Correct | 189 ms | 4536 KB | Output is correct |
4 | Correct | 156 ms | 4536 KB | Output is correct |
5 | Correct | 1698 ms | 7656 KB | Output is correct |
6 | Correct | 1963 ms | 7436 KB | Output is correct |
7 | Correct | 1698 ms | 7596 KB | Output is correct |
8 | Correct | 1130 ms | 4880 KB | Output is correct |
9 | Correct | 1102 ms | 4972 KB | Output is correct |
10 | Correct | 1161 ms | 4928 KB | Output is correct |
11 | Correct | 1873 ms | 6448 KB | Output is correct |
12 | Correct | 1805 ms | 6220 KB | Output is correct |
13 | Correct | 1878 ms | 6128 KB | Output is correct |
14 | Correct | 1726 ms | 7516 KB | Output is correct |
15 | Correct | 1739 ms | 7648 KB | Output is correct |
16 | Correct | 2192 ms | 7488 KB | Output is correct |
17 | Correct | 2174 ms | 7764 KB | Output is correct |
18 | Correct | 2200 ms | 7524 KB | Output is correct |
19 | Correct | 2144 ms | 7572 KB | Output is correct |
20 | Correct | 2185 ms | 6640 KB | Output is correct |
21 | Correct | 2132 ms | 6688 KB | Output is correct |
22 | Correct | 2087 ms | 7440 KB | Output is correct |
23 | Correct | 1840 ms | 6268 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1480 ms | 5724 KB | Output is correct |
2 | Correct | 1547 ms | 5688 KB | Output is correct |
3 | Correct | 1531 ms | 5724 KB | Output is correct |
4 | Correct | 1693 ms | 5648 KB | Output is correct |
5 | Correct | 1705 ms | 5760 KB | Output is correct |
6 | Correct | 2868 ms | 5736 KB | Output is correct |
7 | Correct | 2846 ms | 5840 KB | Output is correct |
8 | Correct | 2827 ms | 5688 KB | Output is correct |
9 | Correct | 61 ms | 2172 KB | Output is correct |
10 | Correct | 1969 ms | 5612 KB | Output is correct |
11 | Correct | 1749 ms | 5596 KB | Output is correct |
12 | Correct | 1749 ms | 5672 KB | Output is correct |
13 | Correct | 1645 ms | 5624 KB | Output is correct |
14 | Correct | 1178 ms | 4776 KB | Output is correct |
15 | Correct | 838 ms | 3460 KB | Output is correct |
16 | Correct | 1401 ms | 5032 KB | Output is correct |
17 | Correct | 1176 ms | 4784 KB | Output is correct |
18 | Correct | 60 ms | 2168 KB | Output is correct |
19 | Correct | 1297 ms | 4860 KB | Output is correct |
20 | Correct | 1075 ms | 4752 KB | Output is correct |
21 | Correct | 982 ms | 4868 KB | Output is correct |
22 | Correct | 893 ms | 5184 KB | Output is correct |
23 | Correct | 831 ms | 5012 KB | Output is correct |
24 | Correct | 924 ms | 4796 KB | Output is correct |
25 | Correct | 811 ms | 4756 KB | Output is correct |
26 | Correct | 1546 ms | 5896 KB | Output is correct |
27 | Correct | 1891 ms | 5796 KB | Output is correct |
28 | Correct | 1660 ms | 5872 KB | Output is correct |
29 | Correct | 1293 ms | 5632 KB | Output is correct |
30 | Correct | 1964 ms | 5624 KB | Output is correct |
31 | Correct | 1979 ms | 5656 KB | Output is correct |
32 | Correct | 1955 ms | 5668 KB | Output is correct |
33 | Correct | 1623 ms | 5620 KB | Output is correct |
34 | Correct | 1645 ms | 5780 KB | Output is correct |
35 | Correct | 1654 ms | 5840 KB | Output is correct |
36 | Correct | 1381 ms | 5620 KB | Output is correct |
37 | Correct | 1358 ms | 5864 KB | Output is correct |
38 | Correct | 1338 ms | 5652 KB | Output is correct |
39 | Correct | 1244 ms | 5648 KB | Output is correct |
40 | Correct | 1247 ms | 5716 KB | Output is correct |
41 | Correct | 1216 ms | 5604 KB | Output is correct |
42 | Correct | 1207 ms | 5584 KB | Output is correct |
43 | Correct | 1225 ms | 5800 KB | Output is correct |
44 | Correct | 1209 ms | 5712 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 34 ms | 1400 KB | Output is correct |
4 | Correct | 10 ms | 504 KB | Output is correct |
5 | Correct | 22 ms | 1400 KB | Output is correct |
6 | Correct | 18 ms | 1272 KB | Output is correct |
7 | Correct | 22 ms | 1368 KB | Output is correct |
8 | Correct | 21 ms | 1272 KB | Output is correct |
9 | Correct | 32 ms | 1404 KB | Output is correct |
10 | Correct | 23 ms | 1272 KB | Output is correct |
11 | Correct | 21 ms | 1272 KB | Output is correct |
12 | Correct | 24 ms | 1272 KB | Output is correct |
13 | Correct | 28 ms | 1400 KB | Output is correct |
14 | Correct | 25 ms | 1400 KB | Output is correct |
15 | Correct | 25 ms | 1400 KB | Output is correct |
16 | Correct | 26 ms | 1400 KB | Output is correct |
17 | Correct | 26 ms | 1384 KB | Output is correct |
18 | Correct | 1480 ms | 5724 KB | Output is correct |
19 | Correct | 1547 ms | 5688 KB | Output is correct |
20 | Correct | 1531 ms | 5724 KB | Output is correct |
21 | Correct | 1693 ms | 5648 KB | Output is correct |
22 | Correct | 1705 ms | 5760 KB | Output is correct |
23 | Correct | 2868 ms | 5736 KB | Output is correct |
24 | Correct | 2846 ms | 5840 KB | Output is correct |
25 | Correct | 2827 ms | 5688 KB | Output is correct |
26 | Correct | 61 ms | 2172 KB | Output is correct |
27 | Correct | 1969 ms | 5612 KB | Output is correct |
28 | Correct | 1749 ms | 5596 KB | Output is correct |
29 | Correct | 1749 ms | 5672 KB | Output is correct |
30 | Correct | 1645 ms | 5624 KB | Output is correct |
31 | Correct | 1178 ms | 4776 KB | Output is correct |
32 | Correct | 838 ms | 3460 KB | Output is correct |
33 | Correct | 1401 ms | 5032 KB | Output is correct |
34 | Correct | 1176 ms | 4784 KB | Output is correct |
35 | Correct | 60 ms | 2168 KB | Output is correct |
36 | Correct | 1297 ms | 4860 KB | Output is correct |
37 | Correct | 1075 ms | 4752 KB | Output is correct |
38 | Correct | 982 ms | 4868 KB | Output is correct |
39 | Correct | 893 ms | 5184 KB | Output is correct |
40 | Correct | 831 ms | 5012 KB | Output is correct |
41 | Correct | 924 ms | 4796 KB | Output is correct |
42 | Correct | 811 ms | 4756 KB | Output is correct |
43 | Correct | 1958 ms | 7552 KB | Output is correct |
44 | Correct | 70 ms | 2168 KB | Output is correct |
45 | Correct | 189 ms | 4536 KB | Output is correct |
46 | Correct | 156 ms | 4536 KB | Output is correct |
47 | Correct | 1698 ms | 7656 KB | Output is correct |
48 | Correct | 1963 ms | 7436 KB | Output is correct |
49 | Correct | 1698 ms | 7596 KB | Output is correct |
50 | Correct | 1130 ms | 4880 KB | Output is correct |
51 | Correct | 1102 ms | 4972 KB | Output is correct |
52 | Correct | 1161 ms | 4928 KB | Output is correct |
53 | Correct | 1873 ms | 6448 KB | Output is correct |
54 | Correct | 1805 ms | 6220 KB | Output is correct |
55 | Correct | 1878 ms | 6128 KB | Output is correct |
56 | Correct | 1726 ms | 7516 KB | Output is correct |
57 | Correct | 1739 ms | 7648 KB | Output is correct |
58 | Correct | 2192 ms | 7488 KB | Output is correct |
59 | Correct | 2174 ms | 7764 KB | Output is correct |
60 | Correct | 2200 ms | 7524 KB | Output is correct |
61 | Correct | 2144 ms | 7572 KB | Output is correct |
62 | Correct | 2185 ms | 6640 KB | Output is correct |
63 | Correct | 2132 ms | 6688 KB | Output is correct |
64 | Correct | 2087 ms | 7440 KB | Output is correct |
65 | Correct | 1840 ms | 6268 KB | Output is correct |
66 | Correct | 1546 ms | 5896 KB | Output is correct |
67 | Correct | 1891 ms | 5796 KB | Output is correct |
68 | Correct | 1660 ms | 5872 KB | Output is correct |
69 | Correct | 1293 ms | 5632 KB | Output is correct |
70 | Correct | 1964 ms | 5624 KB | Output is correct |
71 | Correct | 1979 ms | 5656 KB | Output is correct |
72 | Correct | 1955 ms | 5668 KB | Output is correct |
73 | Correct | 1623 ms | 5620 KB | Output is correct |
74 | Correct | 1645 ms | 5780 KB | Output is correct |
75 | Correct | 1654 ms | 5840 KB | Output is correct |
76 | Correct | 1381 ms | 5620 KB | Output is correct |
77 | Correct | 1358 ms | 5864 KB | Output is correct |
78 | Correct | 1338 ms | 5652 KB | Output is correct |
79 | Correct | 1244 ms | 5648 KB | Output is correct |
80 | Correct | 1247 ms | 5716 KB | Output is correct |
81 | Correct | 1216 ms | 5604 KB | Output is correct |
82 | Correct | 1207 ms | 5584 KB | Output is correct |
83 | Correct | 1225 ms | 5800 KB | Output is correct |
84 | Correct | 1209 ms | 5712 KB | Output is correct |
85 | Correct | 2279 ms | 7932 KB | Output is correct |
86 | Correct | 216 ms | 5528 KB | Output is correct |
87 | Correct | 193 ms | 5400 KB | Output is correct |
88 | Correct | 2146 ms | 8420 KB | Output is correct |
89 | Correct | 2323 ms | 8512 KB | Output is correct |
90 | Correct | 2120 ms | 8196 KB | Output is correct |
91 | Correct | 1684 ms | 5580 KB | Output is correct |
92 | Correct | 1704 ms | 5672 KB | Output is correct |
93 | Correct | 2615 ms | 5656 KB | Output is correct |
94 | Correct | 2496 ms | 7036 KB | Output is correct |
95 | Correct | 2340 ms | 6976 KB | Output is correct |
96 | Correct | 2921 ms | 7108 KB | Output is correct |
97 | Correct | 1846 ms | 8320 KB | Output is correct |
98 | Correct | 1885 ms | 7780 KB | Output is correct |
99 | Correct | 2578 ms | 8044 KB | Output is correct |
100 | Correct | 2519 ms | 8072 KB | Output is correct |
101 | Correct | 2507 ms | 8028 KB | Output is correct |
102 | Correct | 2518 ms | 8048 KB | Output is correct |
103 | Correct | 2951 ms | 7304 KB | Output is correct |
104 | Correct | 2992 ms | 7316 KB | Output is correct |
105 | Correct | 2406 ms | 10732 KB | Output is correct |
106 | Correct | 1994 ms | 10024 KB | Output is correct |
107 | Correct | 2390 ms | 10732 KB | Output is correct |
108 | Correct | 2538 ms | 11532 KB | Output is correct |
109 | Correct | 2404 ms | 9316 KB | Output is correct |