Submission #1271773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271773		thuhienne	Bridges (APIO19_bridges)	C++20	Compilation error	0 ms	0 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define union __union__

const int can = 350;

int n,m,q;

struct __ {
	int u,v,w,index;
	bool operator < (const __ & other) {
		return w < other.w;
	}
} edge[100009];

bool changed[100009];

int uniq,firsttime[100009];

int root[100009],size[100009];

int getroot(int node) {
	return (node == root[node] ? node : root[node] = getroot(root[node]));
}

void union(int u,int v) {
	u = getroot(u),v = getroot(v);
	if (u != v) root[u] = v,size[v] += size[u];
}

struct data {
	int index,rootbefore,sizebefore,rootafter,sizeafter;
};

int getroot(int node,vector <data> & record) {
	if (node == root[node]) return node;
	int d = getroot(root[node],record);
	record.push_back({node,root[node],size[node],d,size[node]});
	root[node] = d;
	return d;
}
void union(int u,int v,vector <data> & record) {
	u = getroot(u,record);
	v = getroot(v,record);
	if (u == v) return;
	
	record.push_back({u,root[u],size[u],v,size[u]});
	root[u] = v;
	
	record.push_back({v,root[v],size[v],root[v],size[v] + size[u]});
	size[v] += size[u];
	
}

void rollback(vector <data> & record) {
	reverse(record.begin(),record.end());
	for (auto d : record) {
		root[d.index] = d.rootbefore;
		size[d.index] = d.sizebefore;
	}
}


struct query {
	int op,x,y,index;
} ask[100009];

__ bridges[100009];

int answer[100009];

int main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	//freopen(".inp","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n >> m;
	for (int i = 1;i <= m;i++) {
		cin >> edge[i].u >> edge[i].v >> edge[i].w;
		edge[i].index = i;
	}
	cin >> q;
	for (int ____ = 0;;____++) {
		int l = max(1,____ * can),r = min(q,(____ + 1)*can - 1);
		
		vector <query> contain;
		
		for (int i = l;i <= r;i++) {
			cin >> ask[i].op >> ask[i].x >> ask[i].y;
			ask[i].index = i;
			if (ask[i].op == 1) {
				changed[ask[i].x] = 1;
				bridges[i] = edge[ask[i].x];
			}
			else contain.push_back(ask[i]);
		}
		
		for (int i = 1;i <= n;i++) root[i] = i,size[i] = 1;
		sort(contain.begin(),contain.end(),[] (query a,query b) {
			return a.y > b.y;
		});
		sort(edge + 1,edge + 1 + m);
		int pt = m + 1;
		
		for (auto d : contain) {
			int minimum = d.y,island = d.x;
			while (pt > 1 && edge[pt - 1].w >= minimum) {
				pt--;
				if (!changed[edge[pt].index]) union(edge[pt].u,edge[pt].v);
			}
			
			vector <data> record;
			
			cout << "BEFORE:\n";
			for (int i = 1;i <= n;i++) cout << root[i] << " ";
			cout << '\n';
			
			uniq++;
			for (int i = d.index - 1;i >= l;i--) if (ask[i].op == 1) {
				cout << "DITCUMAY " << ask[i].x << " " << ask[i].y << '\n';
				
				__ bridge = bridges[i];
				int w = ask[i].y;
				
				if (firsttime[bridge.index] == uniq) continue;
				firsttime[bridge.index] = uniq;
				
				if (w >= minimum) union(bridge.u,bridge.v,record);
			}
			for (int i = d.index + 1;i <= r;i++) if (ask[i].op == 1) {
				__ bridge = bridges[i];
				if (firsttime[bridge.index] == uniq) continue;
				if (bridge.w >= minimum) union(bridge.u,bridge.v,record);
			}
			
			answer[d.index] = size[getroot(island,record)];
			
			rollback(record);
		}
		
		sort(edge + 1,edge + 1 + m,[] (__ a,__ b) {
			return a.index < b.index;
		});
		
		for (int i = l;i <= r;i++) if (ask[i].op == 1) {
			changed[ask[i].x] = 0;
			edge[ask[i].x].w = ask[i].y;
		}
		
		if (r == q) break;
	}
	for (int i = 1;i <= q;i++) if (ask[i].op == 2) cout << answer[i] << '\n';
}

/*
  Nho doi vai em gay
			  co gai ay ngoi duoi goc pho nen tho ...
*/

Compilation message (stderr)

bridges.cpp: In function 'void __union__(int, int)':
bridges.cpp:29:33: error: reference to 'size' is ambiguous
   29 |         if (u != v) root[u] = v,size[v] += size[u];
      |                                 ^~~~
In file included from /usr/include/c++/13/string:53,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from bridges.cpp:1:
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:29:44: error: reference to 'size' is ambiguous
   29 |         if (u != v) root[u] = v,size[v] += size[u];
      |                                            ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp: At global scope:
bridges.cpp:36:34: error: template argument 1 is invalid
   36 | int getroot(int node,vector <data> & record) {
      |                                  ^
bridges.cpp:36:34: error: template argument 2 is invalid
bridges.cpp:36:34: error: template argument 1 is invalid
bridges.cpp:36:34: error: template argument 2 is invalid
bridges.cpp:36:34: error: template argument 1 is invalid
bridges.cpp:36:34: error: template argument 2 is invalid
bridges.cpp:36:34: error: template argument 1 is invalid
bridges.cpp:36:34: error: template argument 2 is invalid
bridges.cpp:36:22: error: invalid template-id
   36 | int getroot(int node,vector <data> & record) {
      |                      ^~~~~~
bridges.cpp:36:30: error: reference to 'data' is ambiguous
   36 | int getroot(int node,vector <data> & record) {
      |                              ^~~~
/usr/include/c++/13/bits/range_access.h:346:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(initializer_list<_Tp>)'
  346 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:336:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  336 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:325:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  325 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:314:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  314 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
bridges.cpp:32:8: note:                 'struct data'
   32 | struct data {
      |        ^~~~
bridges.cpp:36:22: error: missing template argument list after 'std::vector'; template placeholder not permitted in parameter
   36 | int getroot(int node,vector <data> & record) {
      |                      ^~~~~~
      |                            <>
bridges.cpp:36:22: note: or use 'auto' for an abbreviated function template
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:428:11: note: 'template<class _Tp, class _Alloc> class std::vector' declared here
  428 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
bridges.cpp: In function 'int getroot(...)':
bridges.cpp:38:36: error: 'record' was not declared in this scope
   38 |         int d = getroot(root[node],record);
      |                                    ^~~~~~
bridges.cpp:39:43: error: reference to 'size' is ambiguous
   39 |         record.push_back({node,root[node],size[node],d,size[node]});
      |                                           ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:39:56: error: reference to 'size' is ambiguous
   39 |         record.push_back({node,root[node],size[node],d,size[node]});
      |                                                        ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp: At global scope:
bridges.cpp:43:36: error: template argument 1 is invalid
   43 | void union(int u,int v,vector <data> & record) {
      |                                    ^
bridges.cpp:43:36: error: template argument 2 is invalid
bridges.cpp:43:36: error: template argument 1 is invalid
bridges.cpp:43:36: error: template argument 2 is invalid
bridges.cpp:43:36: error: template argument 1 is invalid
bridges.cpp:43:36: error: template argument 2 is invalid
bridges.cpp:43:36: error: template argument 1 is invalid
bridges.cpp:43:36: error: template argument 2 is invalid
bridges.cpp:43:24: error: invalid template-id
   43 | void union(int u,int v,vector <data> & record) {
      |                        ^~~~~~
bridges.cpp:43:32: error: reference to 'data' is ambiguous
   43 | void union(int u,int v,vector <data> & record) {
      |                                ^~~~
/usr/include/c++/13/bits/range_access.h:346:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(initializer_list<_Tp>)'
  346 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:336:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  336 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:325:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  325 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:314:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  314 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
bridges.cpp:32:8: note:                 'struct data'
   32 | struct data {
      |        ^~~~
bridges.cpp:43:24: error: missing template argument list after 'std::vector'; template placeholder not permitted in parameter
   43 | void union(int u,int v,vector <data> & record) {
      |                        ^~~~~~
      |                              <>
bridges.cpp:43:24: note: or use 'auto' for an abbreviated function template
/usr/include/c++/13/bits/stl_vector.h:428:11: note: 'template<class _Tp, class _Alloc> class std::vector' declared here
  428 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
bridges.cpp: In function 'void __union__(...)':
bridges.cpp:44:23: error: 'record' was not declared in this scope
   44 |         u = getroot(u,record);
      |                       ^~~~~~
bridges.cpp:48:37: error: reference to 'size' is ambiguous
   48 |         record.push_back({u,root[u],size[u],v,size[u]});
      |                                     ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:48:47: error: reference to 'size' is ambiguous
   48 |         record.push_back({u,root[u],size[u],v,size[u]});
      |                                               ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:51:37: error: reference to 'size' is ambiguous
   51 |         record.push_back({v,root[v],size[v],root[v],size[v] + size[u]});
      |                                     ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:51:53: error: reference to 'size' is ambiguous
   51 |         record.push_back({v,root[v],size[v],root[v],size[v] + size[u]});
      |                                                     ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:51:63: error: reference to 'size' is ambiguous
   51 |         record.push_back({v,root[v],size[v],root[v],size[v] + size[u]});
      |                                                               ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:52:9: error: reference to 'size' is ambiguous
   52 |         size[v] += size[u];
      |         ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:52:20: error: reference to 'size' is ambiguous
   52 |         size[v] += size[u];
      |                    ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp: At global scope:
bridges.cpp:56:27: error: template argument 1 is invalid
   56 | void rollback(vector <data> & record) {
      |                           ^
bridges.cpp:56:27: error: template argument 2 is invalid
bridges.cpp:56:27: error: template argument 1 is invalid
bridges.cpp:56:27: error: template argument 2 is invalid
bridges.cpp:56:27: error: template argument 1 is invalid
bridges.cpp:56:27: error: template argument 2 is invalid
bridges.cpp:56:27: error: template argument 1 is invalid
bridges.cpp:56:27: error: template argument 2 is invalid
bridges.cpp:56:15: error: invalid template-id
   56 | void rollback(vector <data> & record) {
      |               ^~~~~~
bridges.cpp:56:6: error: variable or field 'rollback' declared void
   56 | void rollback(vector <data> & record) {
      |      ^~~~~~~~
bridges.cpp:56:29: error: missing template arguments before '&' token
   56 | void rollback(vector <data> & record) {
      |                             ^
bridges.cpp:56:31: error: 'record' was not declared in this scope
   56 | void rollback(vector <data> & record) {
      |                               ^~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:98:56: error: reference to 'size' is ambiguous
   98 |                 for (int i = 1;i <= n;i++) root[i] = i,size[i] = 1;
      |                                                        ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:112:37: error: template argument 1 is invalid
  112 |                         vector <data> record;
      |                                     ^
bridges.cpp:112:37: error: template argument 2 is invalid
bridges.cpp:136:43: error: reference to 'size' is ambiguous
  136 |                         answer[d.index] = size[getroot(island,record)];
      |                                           ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:138:25: error: 'rollback' was not declared in this scope
  138 |                         rollback(record);
      |                         ^~~~~~~~