Submission #492026

#TimeUsernameProblemLanguageResultExecution timeMemory
492026robind3r꿈 (IOI13_dreaming)C++17
Compilation error
0 ms0 KiB
#include "dreaming.h" #include <bits/stdc++.h> vector<int> to, sz; //ez union find 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; } int find(int x){ if(x==link[x]) return x; return to[x] = find(to[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:4:1: error: 'vector' does not name a type
    4 | vector<int> to, sz;
      | ^~~~~~
dreaming.cpp: In function 'void unite(int, int)':
dreaming.cpp:8:13: error: 'find' was not declared in this scope; did you mean 'std::find'?
    8 |     int x = find(u);
      |             ^~~~
      |             std::find
In file included 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/pstl/glue_algorithm_defs.h:60:1: note: 'std::find' declared here
   60 | find(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~
dreaming.cpp:12:9: error: 'sz' was not declared in this scope
   12 |     if (sz[x] < sz[y])swap(x, y);
      |         ^~
dreaming.cpp:12:23: error: 'swap' was not declared in this scope
   12 |     if (sz[x] < sz[y])swap(x, y);
      |                       ^~~~
dreaming.cpp:12:23: 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 dreaming.cpp:2:
/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 dreaming.cpp:2:
/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 dreaming.cpp:2:
/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 dreaming.cpp:2:
/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); }
      |               ^~~~
dreaming.cpp:13:5: error: 'sz' was not declared in this scope
   13 |     sz[x]+=sz[y];
      |     ^~
dreaming.cpp:14:5: error: 'to' was not declared in this scope; did you mean 'tm'?
   14 |     to[y] = x;
      |     ^~
      |     tm
dreaming.cpp: In function 'int find(int)':
dreaming.cpp:18:8: error: 'link' was not declared in this scope
   18 |  if(x==link[x]) return x;
      |        ^~~~
dreaming.cpp:19:12: error: 'to' was not declared in this scope; did you mean 'tm'?
   19 |     return to[x] = find(to[x]);
      |            ^~
      |            tm
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:33:2: error: 'vector' was not declared in this scope
   33 |  vector<pair<int, int>> node[N]; //node[a] = {b, w}
      |  ^~~~~~
dreaming.cpp:33: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 dreaming.cpp:2:
/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 dreaming.cpp:2:
/usr/include/c++/10/vector:86:13: note:   'std::pmr::vector'
   86 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
dreaming.cpp:33:9: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   33 |  vector<pair<int, int>> node[N]; //node[a] = {b, w}
      |         ^~~~
      |         std::pair
In file included 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 dreaming.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'std::pair' declared here
  211 |     struct pair
      |            ^~~~
dreaming.cpp:33:14: error: expected primary-expression before 'int'
   33 |  vector<pair<int, int>> node[N]; //node[a] = {b, w}
      |              ^~~
dreaming.cpp:34:14: error: expected primary-expression before 'int'
   34 |  vector<pair<int, int>> nodec[N]; //node[a] = {b, w}
      |              ^~~
dreaming.cpp:35:14: error: expected primary-expression before 'int'
   35 |  vector<pair<int, int>> noded[N]; //node[a] = {b, w}
      |              ^~~
dreaming.cpp:37:9: error: 'tuple' was not declared in this scope; did you mean 'std::tuple'?
   37 |  vector<tuple<int, int, int>> edges;
      |         ^~~~~
      |         std::tuple
In file included from /usr/include/c++/10/bits/move.h:57,
                 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 dreaming.cpp:2:
/usr/include/c++/10/type_traits:2631:11: note: 'std::tuple' declared here
 2631 |     class tuple;
      |           ^~~~~
dreaming.cpp:37:15: error: expected primary-expression before 'int'
   37 |  vector<tuple<int, int, int>> edges;
      |               ^~~
dreaming.cpp:43:15: error: 'node' was not declared in this scope
   43 |  auto dfs = [&node, &comp, &dfs](int i, int n){
      |               ^~~~
dreaming.cpp:43:29: error: use of 'dfs' before deduction of 'auto'
   43 |  auto dfs = [&node, &comp, &dfs](int i, int n){
      |                             ^~~
dreaming.cpp: In lambda function:
dreaming.cpp:44:6: error: 'visited' is not captured
   44 |   if(visited[i])return;
      |      ^~~~~~~
dreaming.cpp:43:32: note: the lambda has no capture-default
   43 |  auto dfs = [&node, &comp, &dfs](int i, int n){
      |                                ^
dreaming.cpp:40:7: note: 'bool visited [N]' declared here
   40 |  bool visited[N];
      |       ^~~~~~~
dreaming.cpp:45:3: error: 'visited' is not captured
   45 |   visited[i] = true;
      |   ^~~~~~~
dreaming.cpp:43:32: note: the lambda has no capture-default
   43 |  auto dfs = [&node, &comp, &dfs](int i, int n){
      |                                ^
dreaming.cpp:40:7: note: 'bool visited [N]' declared here
   40 |  bool visited[N];
      |       ^~~~~~~
dreaming.cpp:47:16: error: 'node' is not captured
   47 |   for(auto e : node[i])dfs(e.first, n);
      |                ^~~~
dreaming.cpp:43:32: note: the lambda has no capture-default
   43 |  auto dfs = [&node, &comp, &dfs](int i, int n){
      |                                ^
dreaming.cpp:43:15: note: '<typeprefixerror>node' declared here
   43 |  auto dfs = [&node, &comp, &dfs](int i, int n){
      |               ^~~~
dreaming.cpp:47:24: error: use of 'dfs' before deduction of 'auto'
   47 |   for(auto e : node[i])dfs(e.first, n);
      |                        ^~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:50:2: error: expected ',' or ';' before 'for'
   50 |  for(int i = 0; i < M; i++){
      |  ^~~
dreaming.cpp:50:17: error: 'i' was not declared in this scope
   50 |  for(int i = 0; i < M; i++){
      |                 ^
dreaming.cpp:81:9: error: expected primary-expression before 'int'
   81 |  vector<int> ord;
      |         ^~~
dreaming.cpp:85:7: error: 'nodec' was not declared in this scope
   85 |    if(nodec[i].size() == 1){
      |       ^~~~~
dreaming.cpp:89:8: error: 'ord' was not declared in this scope
   89 |        ord.push_back(i);
      |        ^~~
dreaming.cpp:97:9: error: expected primary-expression before 'int'
   97 |  vector<int> maxer(N), fin(N, -1);
      |         ^~~
dreaming.cpp:100:3: error: 't' was not declared in this scope
  100 |   t = ord[i];
      |   ^
dreaming.cpp:100:7: error: 'ord' was not declared in this scope
  100 |   t = ord[i];
      |       ^~~
dreaming.cpp:101:6: error: 'noded' was not declared in this scope
  101 |   if(noded[t].size() == 1){
      |      ^~~~~
dreaming.cpp:102:8: error: 'maxer' was not declared in this scope
  102 |    if((maxer[t] + noded[t][0].second) > maxer[noded[t][0].first]){
      |        ^~~~~
dreaming.cpp:104:5: error: 'fin' was not declared in this scope; did you mean 'find'?
  104 |     fin[comp[noded[t][0].first]] = noded[t][0].first;
      |     ^~~
      |     find
dreaming.cpp:123:7: error: 'fin' was not declared in this scope; did you mean 'finq'?
  123 |    if(fin[i]!=-1)finq = fin[i];
      |       ^~~
      |       finq
dreaming.cpp:126:4: error: 'edges' was not declared in this scope
  126 |    edges[i].push_back({L, i, finq});
      |    ^~~~~
dreaming.cpp:135:7: error: 'edges' was not declared in this scope
  135 |  sort(edges.rbegin(), edges.rend());
      |       ^~~~~
dreaming.cpp:135:2: error: 'sort' was not declared in this scope; did you mean 'std::sort'?
  135 |  sort(edges.rbegin(), edges.rend());
      |  ^~~~
      |  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 dreaming.cpp:2:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:296:1: note: 'std::sort' declared here
  296 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
      | ^~~~
dreaming.cpp:136:2: error: 'to' was not declared in this scope; did you mean 'tm'?
  136 |  to.resize(N);
      |  ^~
      |  tm
dreaming.cpp:137:2: error: 'sz' was not declared in this scope
  137 |  sz.resize(N, 0);
      |  ^~
dreaming.cpp:138:2: error: 'iota' was not declared in this scope; did you mean 'std::iota'?
  138 |  iota(to.begin(), to.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 dreaming.cpp:2:
/usr/include/c++/10/bits/stl_numeric.h:88:5: note: 'std::iota' declared here
   88 |     iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
      |     ^~~~
dreaming.cpp:142:12: error: 'get' was not declared in this scope; did you mean 'std::get'?
  142 |   if(!same(get<1>(e), get<2>(e))){
      |            ^~~
      |            std::get
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from dreaming.cpp:2:
/usr/include/c++/10/variant:1099:27: note: 'std::get' declared here
 1099 |     constexpr const _Tp&& get(const variant<_Types...>&& __v)
      |                           ^~~