Submission #492029

#	Time	Username	Problem	Language	Result	Execution time	Memory
492029		robind3r	Dreaming (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> to, sz;

//ez union find

int find(int x){
	if(x==link[x]) return x;
    return to[x] = find(to[x]);
}

void unite(int u, int v){
    int x = find(u);
    int y = find(v);
    if (x == y)
        return;
    if (sz[x] < sz[y])swap(x, y);
    sz[x]+=sz[y];
    to[y] = x;
}

bool same(int u, int v){
	return find(u) == find(v);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	//first step: find optimal point in which to add the new edge (for each component)
	//this can be done by starting from the bottom and finding the maximum from each side of the tree
	//we need to recursively find the nodes that only have one (zero?!) (unvisited) edge(s)
	//can probably be done with good time complexity but idk (i think it could become O(NlogN)? probably N squared done lazily)
	
	//from the input data we can easily create a vector<>[] representation as follows
	vector<pair<int, int>> node[N]; //node[a] = {b, w}
	vector<pair<int, int>> nodec[N]; //node[a] = {b, w}
	vector<pair<int, int>> noded[N]; //node[a] = {b, w}
	
	vector<tuple<int, int, int>> edges;
	
	int comp[N];
	bool visited[N];
	
	//epic dfs lambda
	auto dfs = [&node, &comp, &dfs](int i, int n){
		if(visited[i])return;
		visited[i] = true;
		comp[i] = n;
		for(auto e : node[i])dfs(e.first, n);
	}
	
	for(int i = 0; i < M; i++){
		node[A[i]].push_back({B[i], T[i]});
		node[B[i]].push_back({A[i], T[i]});
		
		nodec[A[i]].push_back({B[i], T[i]});
		nodec[B[i]].push_back({A[i], T[i]});
		
		noded[A[i]].push_back({B[i], T[i]});
		noded[B[i]].push_back({A[i], T[i]});//it sets it 3 times because i was too lazy to let it copy later on in the code
		
		edges.push_back(A[i], B[i], T[i]);
		edges.push_back(B[i], A[i], T[i]);//for kruskal
	}
	
	//dfs to find the separate components
	for(int i = 0; i < N; i++)dfs(i, i);
	
	//next, we need to recursively find the tree "endings"
	//we just need to check if the number of edges coming in is 0...
	//we can probably do this for the whole tree with help from some array
	
	/*int numin[N];

	for(int i = 0; i < N; i++)numin[i] = 0;
	
	for(int i = 0; i < N; i++){
		for(auto e : node[i]){
			numin[e.first]++;
		}
	}*/
	
	vector<int> ord;
	
	while(true){
		for(int i = 0; i < N; i++){
			if(nodec[i].size() == 1){
				for (auto it : nodec[nodec[i][0].first]) {
					if(*it==i)nodec[nodec[i][0].first].erase(it);
    			}
    			ord.push_back(i);
    			if(ord.size()==N)goto el;
			}
		}
	}
	
	el:
	
	vector<int> maxer(N), fin(N, -1);
	
	for(int i = 0; i < N; i++){
		t = ord[i];
		if(noded[t].size() == 1){
			if((maxer[t] + noded[t][0].second) > maxer[noded[t][0].first]){
				maxer[noded[t][0].first] = maxer[t] + noded[t][0].second;
				fin[comp[noded[t][0].first]] = noded[t][0].first;
			}
			for (auto it : noded[noded[t][0].first]) {
				if(*it==t){
					noded[noded[t][0].first].erase(it);
				}
    		}
		}
	}
	
	//ideally, the algorithm should be optimized to a better time complexity (finding the best vertex to connect can probably be done faster with the same idea)
	//for it to work with the whole input, the different slots should be permutated (maybe??? or Mst recalced every time???????)
	
	//let's complete (inaccurately) for M = N-2
	//join the two ideal vertices and then calculate the Mst
	
	int finq = -1;
	for(int i = 0; i < N; i++){
		if(finq==-1){
			if(fin[i]!=-1)finq = fin[i];
		}else{
			//assuming that M is equal to N-2
			edges[i].push_back({L, i, finq});
			edges[i].push_back({L, finq, i});
		}
	}
	
	//we now should theoretically have a fully connected graph of which we should find the maximum spanning tree
	//the solution to the problem will be equal to the final maximum spanning tree
	//we can easily implement the maximum spanning tree using a union-find structure
	
	sort(edges.rbegin(), edges.rend());
	to.resize(N);
	sz.resize(N, 0);
	iota(to.begin(), to.end(), 0);
	
	int tot = 0;
	for(auto e : edges){
		if(!same(get<1>(e), get<2>(e))){
			unite(get<1>(e), get<2>(e));
			tot+=get<0>(e);
		}
	}

    return tot;
}

Compilation message (stderr)

dreaming.cpp: In function 'int find(int)':
dreaming.cpp:11:8: error: 'link' was not declared in this scope
   11 |  if(x==link[x]) return x;
      |        ^~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:46:29: error: use of 'dfs' before deduction of 'auto'
   46 |  auto dfs = [&node, &comp, &dfs](int i, int n){
      |                             ^~~
dreaming.cpp: In lambda function:
dreaming.cpp:47:6: error: 'visited' is not captured
   47 |   if(visited[i])return;
      |      ^~~~~~~
dreaming.cpp:46:32: note: the lambda has no capture-default
   46 |  auto dfs = [&node, &comp, &dfs](int i, int n){
      |                                ^
dreaming.cpp:43:7: note: 'bool visited [N]' declared here
   43 |  bool visited[N];
      |       ^~~~~~~
dreaming.cpp:48:3: error: 'visited' is not captured
   48 |   visited[i] = true;
      |   ^~~~~~~
dreaming.cpp:46:32: note: the lambda has no capture-default
   46 |  auto dfs = [&node, &comp, &dfs](int i, int n){
      |                                ^
dreaming.cpp:43:7: note: 'bool visited [N]' declared here
   43 |  bool visited[N];
      |       ^~~~~~~
dreaming.cpp:50:24: error: use of 'dfs' before deduction of 'auto'
   50 |   for(auto e : node[i])dfs(e.first, n);
      |                        ^~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:53:2: error: expected ',' or ';' before 'for'
   53 |  for(int i = 0; i < M; i++){
      |  ^~~
dreaming.cpp:53:17: error: 'i' was not declared in this scope
   53 |  for(int i = 0; i < M; i++){
      |                 ^
dreaming.cpp:90:9: error: no match for 'operator*' (operand type is 'std::pair<int, int>')
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |         ^~~
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from dreaming.cpp:2:
/usr/include/c++/10/complex:391:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const std::complex<_Tp>&)'
  391 |     operator*(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:391:5: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   'std::pair<int, int>' is not derived from 'const std::complex<_Tp>'
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from dreaming.cpp:2:
/usr/include/c++/10/complex:400:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const _Tp&)'
  400 |     operator*(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:400:5: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   'std::pair<int, int>' is not derived from 'const std::complex<_Tp>'
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from dreaming.cpp:2:
/usr/include/c++/10/complex:409:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const _Tp&, const std::complex<_Tp>&)'
  409 |     operator*(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:409:5: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   candidate expects 2 arguments, 1 provided
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from dreaming.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   'std::pair<int, int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from dreaming.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   'std::pair<int, int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from dreaming.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const typename _Dom::value_type&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   candidate expects 2 arguments, 1 provided
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from dreaming.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::valarray<typename _Dom::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   'std::pair<int, int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from dreaming.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::valarray<typename _Dom::value_type>&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   candidate expects 2 arguments, 1 provided
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from dreaming.cpp:2:
/usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const std::valarray<_Tp>&, const std::valarray<_Tp>&)'
 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1187:1: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   'std::pair<int, int>' is not derived from 'const std::valarray<_Tp>'
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from dreaming.cpp:2:
/usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const std::valarray<_Tp>&, const typename std::valarray<_Tp>::value_type&)'
 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1187:1: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   'std::pair<int, int>' is not derived from 'const std::valarray<_Tp>'
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from dreaming.cpp:2:
/usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const typename std::valarray<_Tp>::value_type&, const std::valarray<_Tp>&)'
 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1187:1: note:   template argument deduction/substitution failed:
dreaming.cpp:90:10: note:   candidate expects 2 arguments, 1 provided
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |          ^~
dreaming.cpp:90:49: error: no matching function for call to 'std::vector<std::pair<int, int> >::erase(std::pair<int, int>&)'
   90 |      if(*it==i)nodec[nodec[i][0].first].erase(it);
      |                                                 ^
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 dreaming.cpp:2:
/usr/include/c++/10/bits/stl_vector.h:1430:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(std::vector<_Tp, _Alloc>::const_iterator) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::iterator = std::vector<std::pair<int, int> >::iterator; std::vector<_Tp, _Alloc>::const_iterator = std::vector<std::pair<int, int> >::const_iterator]'
 1430 |       erase(const_iterator __position)
      |       ^~~~~
/usr/include/c++/10/bits/stl_vector.h:1430:28: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::vector<std::pair<int, int> >::const_iterator'
 1430 |       erase(const_iterator __position)
      |             ~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1457:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::const_iterator) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::iterator = std::vector<std::pair<int, int> >::iterator; std::vector<_Tp, _Alloc>::const_iterator = std::vector<std::pair<int, int> >::const_iterator]'
 1457 |       erase(const_iterator __first, const_iterator __last)
      |       ^~~~~
/usr/include/c++/10/bits/stl_vector.h:1457:7: note:   candidate expects 2 arguments, 1 provided
dreaming.cpp:93:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |        if(ord.size()==N)goto el;
      |           ~~~~~~~~~~^~~
dreaming.cpp:103:3: error: 't' was not declared in this scope
  103 |   t = ord[i];
      |   ^
dreaming.cpp:129:13: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> >, std::tuple<int, int, int> >::value_type' {aka 'class std::tuple<int, int, int>'} has no member named 'push_back'
  129 |    edges[i].push_back({L, i, finq});
      |             ^~~~~~~~~
dreaming.cpp:130:13: error: '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, int> >, std::tuple<int, int, int> >::value_type' {aka 'class std::tuple<int, int, int>'} has no member named 'push_back'
  130 |    edges[i].push_back({L, finq, i});
      |             ^~~~~~~~~