Submission #1045966

#TimeUsernameProblemLanguageResultExecution timeMemory
1045966NotLinuxBridges (APIO19_bridges)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namesapce std; #ifdef DEBUG #include "debug.h" #else #define debug(...) void(23) #endif constexpr int maxN = int(1E5) + 5; constexpr int SQRT = 634; struct DSU { vector<int> par, siz; vector<pair<int&, int>> history; DSU() : DSU(0) {} DSU(int n) { init(n); } void init(int n) { par.assign(n, 0); siz.assign(n, 1); iota(par.begin(), par.end(), 0); } int get(int x) { while(x != par[x]) { x = par[x]; } return x; } bool unite(int a, int b) { a = get(a), b = get(b); if(a == b) { return false; } else if(siz[a] > siz[b]) { swap(a, b); } history.emplace_back(par[a], a); history.emplace_back(siz[b], siz[b]); par[a] = b; siz[b] += siz[a]; return true; } int size(int x) { return siz[get(x)]; } void roll() { history.back().first = history.back().second; history.pop_back(); history.back().first = history.back().second; history.pop_back(); } int snap() { return history.size(); } }; vector<int> g[maxN]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<int> A(M), B(M), C(M), idx(M); for(int i = 0; i < M; ++i) { cin >> A[i] >> B[i] >> C[i]; --A[i], --B[i]; } int Q; cin >> Q; vector<int> T(Q), X(Q), Y(Q); for(int i = 0; i < Q; ++i) { cin >> T[i] >> X[i] >> Y[i]; if(T[i] == 1) { --X[i]; } else { --X[i]; } } debug("wtf"); vector<int> ans(Q, -1); vector<bool> changed(M); for(int l = 0; l < Q; l += SQRT) { int r = min(Q, l + SQRT); vector<int> qq; for(int i = l; i < r; ++i) { if(T[i] == 1) { changed[X[i]] = true; g[X[i]].emplace_back(i); } else { qq.emplace_back(i); } } vector<int> nope, yep; for(int i = 0; i < M; ++i) { if(!changed[i]) { nope.emplace_back(i); } else { yep.emplace_back(i); } } sort(qq.begin(), qq.end(), [&](int lhs, int rhs) { return Y[lhs] > Y[rhs]; }); sort(nope.begin(), nope.end(), [&](int lhs, int rhs) { return C[lhs] > C[rhs]; }); debug(nope, yep); DSU dsu(N); int ptr = 0; for(int i : qq) { debug(i, X[i], Y[i]); while(ptr < int(nope.size()) && C[nope[ptr]] >= Y[i]) { debug(nope[ptr], A[nope[ptr]], B[nope[ptr]]); dsu.unite(A[nope[ptr]], B[nope[ptr]]); ++ptr; } int s = dsu.snap(); for(int j : yep) { debug(j); auto it = upper_bound(g[j].begin(), g[j].end(), i); int cost; if(it == g[j].begin()) { cost = C[j]; } else { --it; cost = Y[*it]; } debug(cost, A[j], B[j]); if(cost >= Y[i]) { debug("united"); dsu.unite(A[j], B[j]); } debug("finished"); } #ifdef DEBUG for(int k = 0; k < N; ++k) { debug(dsu.get(k), dsu.size(k)); } #endif ans[i] = dsu.size(X[i]); while(dsu.snap() != s) { dsu.roll(); } debug("yey\n\n"); } debug("bruh"); for(int i = l; i < r; ++i) { if(T[i] == 1) { g[X[i]].pop_back(); changed[X[i]] = false; C[X[i]] = Y[i]; } } debug("wtf"); } for(int i = 0; i < Q; ++i) { if(ans[i] != -1) { cout << ans[i] << '\n'; } } return 0; }

Compilation message (stderr)

bridges.cpp:2:7: error: expected nested-name-specifier before 'namesapce'
    2 | using namesapce std;
      |       ^~~~~~~~~
bridges.cpp:13:2: error: 'vector' does not name a type
   13 |  vector<int> par, siz;
      |  ^~~~~~
bridges.cpp:14:2: error: 'vector' does not name a type
   14 |  vector<pair<int&, int>> history;
      |  ^~~~~~
bridges.cpp: In member function 'void DSU::init(int)':
bridges.cpp:18:3: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   18 |   par.assign(n, 0);
      |   ^~~
      |   __pstl::execution::v1::par
In file included from /usr/include/c++/10/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridges.cpp:1:
/usr/include/c++/10/pstl/execution_defs.h:111:27: note: '__pstl::execution::v1::par' declared here
  111 | constexpr parallel_policy par{};
      |                           ^~~
bridges.cpp:19:3: error: 'siz' was not declared in this scope; did you mean 'size'?
   19 |   siz.assign(n, 1);
      |   ^~~
      |   size
bridges.cpp:20:3: error: 'iota' was not declared in this scope; did you mean 'std::iota'?
   20 |   iota(par.begin(), par.end(), 0);
      |   ^~~~
      |   std::iota
In file included from /usr/include/c++/10/numeric:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:84,
                 from bridges.cpp:1:
/usr/include/c++/10/bits/stl_numeric.h:88:5: note: 'std::iota' declared here
   88 |     iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
      |     ^~~~
bridges.cpp: In member function 'int DSU::get(int)':
bridges.cpp:23:14: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   23 |   while(x != par[x]) {
      |              ^~~
      |              __pstl::execution::v1::par
In file included from /usr/include/c++/10/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridges.cpp:1:
/usr/include/c++/10/pstl/execution_defs.h:111:27: note: '__pstl::execution::v1::par' declared here
  111 | constexpr parallel_policy par{};
      |                           ^~~
bridges.cpp: In member function 'bool DSU::unite(int, int)':
bridges.cpp:32:13: error: 'siz' was not declared in this scope; did you mean 'size'?
   32 |   } else if(siz[a] > siz[b]) {
      |             ^~~
      |             size
bridges.cpp:33:4: error: 'swap' was not declared in this scope
   33 |    swap(a, b);
      |    ^~~~
bridges.cpp:33:4: note: suggested alternatives:
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from bridges.cpp:1:
/usr/include/c++/10/bits/regex.h:2141:5: note:   'std::__cxx11::swap'
 2141 |     swap(match_results<_Bi_iter, _Alloc>& __lhs,
      |     ^~~~
In file included from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from bridges.cpp:1:
/usr/include/c++/10/bits/move.h:189:5: note:   'std::swap'
  189 |     swap(_Tp& __a, _Tp& __b)
      |     ^~~~
/usr/include/c++/10/bits/move.h:189:5: note:   'std::swap'
In file included from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from bridges.cpp:1:
/usr/include/c++/10/bits/exception_ptr.h:169:5: note:   'std::__exception_ptr::swap'
  169 |     swap(exception_ptr& __lhs, exception_ptr& __rhs)
      |     ^~~~
In file included from /usr/include/c++/10/filesystem:45,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from bridges.cpp:1:
/usr/include/c++/10/bits/fs_path.h:658:15: note:   'std::filesystem::__cxx11::swap'
  658 |   inline void swap(path& __lhs, path& __rhs) noexcept { __lhs.swap(__rhs); }
      |               ^~~~
bridges.cpp:35:3: error: 'history' was not declared in this scope
   35 |   history.emplace_back(par[a], a);
      |   ^~~~~~~
bridges.cpp:35:24: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   35 |   history.emplace_back(par[a], a);
      |                        ^~~
      |                        __pstl::execution::v1::par
In file included from /usr/include/c++/10/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridges.cpp:1:
/usr/include/c++/10/pstl/execution_defs.h:111:27: note: '__pstl::execution::v1::par' declared here
  111 | constexpr parallel_policy par{};
      |                           ^~~
bridges.cpp:36:24: error: 'siz' was not declared in this scope; did you mean 'size'?
   36 |   history.emplace_back(siz[b], siz[b]);
      |                        ^~~
      |                        size
bridges.cpp: In member function 'int DSU::size(int)':
bridges.cpp:42:10: error: 'siz' was not declared in this scope; did you mean 'size'?
   42 |   return siz[get(x)];
      |          ^~~
      |          size
bridges.cpp: In member function 'void DSU::roll()':
bridges.cpp:45:3: error: 'history' was not declared in this scope
   45 |   history.back().first = history.back().second;
      |   ^~~~~~~
bridges.cpp: In member function 'int DSU::snap()':
bridges.cpp:51:10: error: 'history' was not declared in this scope
   51 |   return history.size();
      |          ^~~~~~~
bridges.cpp: At global scope:
bridges.cpp:55:1: error: 'vector' does not name a type
   55 | vector<int> g[maxN];
      | ^~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:58:2: error: 'ios_base' has not been declared
   58 |  ios_base::sync_with_stdio(false);
      |  ^~~~~~~~
bridges.cpp:59:2: error: 'cin' was not declared in this scope; did you mean 'std::cin'?
   59 |  cin.tie(nullptr);
      |  ^~~
      |  std::cin
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
                 from bridges.cpp:1:
/usr/include/c++/10/iostream:60:18: note: 'std::cin' declared here
   60 |   extern istream cin;  /// Linked to standard input
      |                  ^~~
bridges.cpp:63:2: error: 'vector' was not declared in this scope
   63 |  vector<int> A(M), B(M), C(M), idx(M);
      |  ^~~~~~
bridges.cpp:63:2: note: suggested alternatives:
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridges.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note:   'std::vector'
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
In file included from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridges.cpp:1:
/usr/include/c++/10/vector:86:13: note:   'std::pmr::vector'
   86 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
bridges.cpp:63:9: error: expected primary-expression before 'int'
   63 |  vector<int> A(M), B(M), C(M), idx(M);
      |         ^~~
bridges.cpp:65:10: error: 'A' was not declared in this scope
   65 |   cin >> A[i] >> B[i] >> C[i];
      |          ^
bridges.cpp:65:18: error: 'B' was not declared in this scope
   65 |   cin >> A[i] >> B[i] >> C[i];
      |                  ^
bridges.cpp:65:26: error: 'C' was not declared in this scope
   65 |   cin >> A[i] >> B[i] >> C[i];
      |                          ^
bridges.cpp:70:9: error: expected primary-expression before 'int'
   70 |  vector<int> T(Q), X(Q), Y(Q);
      |         ^~~
bridges.cpp:72:10: error: 'T' was not declared in this scope
   72 |   cin >> T[i] >> X[i] >> Y[i];
      |          ^
bridges.cpp:72:18: error: 'X' was not declared in this scope
   72 |   cin >> T[i] >> X[i] >> Y[i];
      |                  ^
bridges.cpp:72:26: error: 'Y' was not declared in this scope
   72 |   cin >> T[i] >> X[i] >> Y[i];
      |                          ^
bridges.cpp:82:9: error: expected primary-expression before 'int'
   82 |  vector<int> ans(Q, -1);
      |         ^~~
bridges.cpp:83:9: error: expected primary-expression before 'bool'
   83 |  vector<bool> changed(M);
      |         ^~~~
bridges.cpp:85:11: error: 'min' was not declared in this scope; did you mean 'std::min'?
   85 |   int r = min(Q, l + SQRT);
      |           ^~~
      |           std::min
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridges.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: 'std::min' declared here
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
bridges.cpp:86:10: error: expected primary-expression before 'int'
   86 |   vector<int> qq;
      |          ^~~
bridges.cpp:88:7: error: 'T' was not declared in this scope
   88 |    if(T[i] == 1) {
      |       ^
bridges.cpp:89:5: error: 'changed' was not declared in this scope
   89 |     changed[X[i]] = true;
      |     ^~~~~~~
bridges.cpp:89:13: error: 'X' was not declared in this scope
   89 |     changed[X[i]] = true;
      |             ^
bridges.cpp:90:5: error: 'g' was not declared in this scope
   90 |     g[X[i]].emplace_back(i);
      |     ^
bridges.cpp:92:5: error: 'qq' was not declared in this scope
   92 |     qq.emplace_back(i);
      |     ^~
bridges.cpp:95:10: error: expected primary-expression before 'int'
   95 |   vector<int> nope, yep;
      |          ^~~
bridges.cpp:97:8: error: 'changed' was not declared in this scope
   97 |    if(!changed[i]) {
      |        ^~~~~~~
bridges.cpp:98:5: error: 'nope' was not declared in this scope
   98 |     nope.emplace_back(i);
      |     ^~~~
bridges.cpp:100:5: error: 'yep' was not declared in this scope
  100 |     yep.emplace_back(i);
      |     ^~~
bridges.cpp:104:8: error: 'qq' was not declared in this scope
  104 |   sort(qq.begin(), qq.end(), [&](int lhs, int rhs) {
      |        ^~
bridges.cpp: In lambda function:
bridges.cpp:105:11: error: 'Y' was not declared in this scope
  105 |    return Y[lhs] > Y[rhs];
      |           ^
bridges.cpp: In function 'int main()':
bridges.cpp:104:3: error: 'sort' was not declared in this scope; did you mean 'std::sort'?
  104 |   sort(qq.begin(), qq.end(), [&](int lhs, int rhs) {
      |   ^~~~
      |   std::sort
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridges.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:296:1: note: 'std::sort' declared here
  296 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
      | ^~~~
bridges.cpp:107:8: error: 'nope' was not declared in this scope
  107 |   sort(nope.begin(), nope.end(), [&](int lhs, int rhs) {
      |        ^~~~
bridges.cpp: In lambda function:
bridges.cpp:108:11: error: 'C' was not declared in this scope
  108 |    return C[lhs] > C[rhs];
      |           ^
bridges.cpp: In function 'int main()':
bridges.cpp:117:36: error: 'C' was not declared in this scope
  117 |    while(ptr < int(nope.size()) && C[nope[ptr]] >= Y[i]) {
      |                                    ^
bridges.cpp:117:52: error: 'Y' was not declared in this scope
  117 |    while(ptr < int(nope.size()) && C[nope[ptr]] >= Y[i]) {
      |                                                    ^
bridges.cpp:119:15: error: 'A' was not declared in this scope
  119 |     dsu.unite(A[nope[ptr]], B[nope[ptr]]);
      |               ^
bridges.cpp:119:29: error: 'B' was not declared in this scope
  119 |     dsu.unite(A[nope[ptr]], B[nope[ptr]]);
      |                             ^
bridges.cpp:123:16: error: 'yep' was not declared in this scope
  123 |    for(int j : yep) {
      |                ^~~
bridges.cpp:125:27: error: 'g' was not declared in this scope
  125 |     auto it = upper_bound(g[j].begin(), g[j].end(), i);
      |                           ^
bridges.cpp:125:15: error: 'upper_bound' was not declared in this scope; did you mean 'std::upper_bound'?
  125 |     auto it = upper_bound(g[j].begin(), g[j].end(), i);
      |               ^~~~~~~~~~~
      |               std::upper_bound
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from bridges.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:2118:5: note: 'std::upper_bound' declared here
 2118 |     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
bridges.cpp:128:13: error: 'C' was not declared in this scope
  128 |      cost = C[j];
      |             ^
bridges.cpp:131:13: error: 'Y' was not declared in this scope
  131 |      cost = Y[*it];
      |             ^
bridges.cpp:134:16: error: 'Y' was not declared in this scope
  134 |     if(cost >= Y[i]) {
      |                ^
bridges.cpp:136:16: error: 'A' was not declared in this scope
  136 |      dsu.unite(A[j], B[j]);
      |                ^
bridges.cpp:136:22: error: 'B' was not declared in this scope
  136 |      dsu.unite(A[j], B[j]);
      |                      ^
bridges.cpp:145:4: error: 'ans' was not declared in this scope; did you mean 'abs'?
  145 |    ans[i] = dsu.size(X[i]);
      |    ^~~
      |    abs
bridges.cpp:145:22: error: 'X' was not declared in this scope
  145 |    ans[i] = dsu.size(X[i]);
      |                      ^
bridges.cpp:154:7: error: 'T' was not declared in this scope
  154 |    if(T[i] == 1) {
      |       ^
bridges.cpp:155:5: error: 'g' was not declared in this scope
  155 |     g[X[i]].pop_back();
      |     ^
bridges.cpp:155:7: error: 'X' was not declared in this scope
  155 |     g[X[i]].pop_back();
      |       ^
bridges.cpp:156:5: error: 'changed' was not declared in this scope
  156 |     changed[X[i]] = false;
      |     ^~~~~~~
bridges.cpp:157:5: error: 'C' was not declared in this scope
  157 |     C[X[i]] = Y[i];
      |     ^
bridges.cpp:157:15: error: 'Y' was not declared in this scope
  157 |     C[X[i]] = Y[i];
      |               ^
bridges.cpp:164:6: error: 'ans' was not declared in this scope; did you mean 'abs'?
  164 |   if(ans[i] != -1) {
      |      ^~~
      |      abs
bridges.cpp:165:4: error: 'cout' was not declared in this scope; did you mean 'std::cout'?
  165 |    cout << ans[i] << '\n';
      |    ^~~~
      |    std::cout
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
                 from bridges.cpp:1:
/usr/include/c++/10/iostream:61:18: note: 'std::cout' declared here
   61 |   extern ostream cout;  /// Linked to standard output
      |                  ^~~~