Submission #1045966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045966		NotLinux	다리 (APIO19_bridges)	C++17	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

bridges

#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
      |                  ^~~~