Submission #362527

#	Time	Username	Problem	Language	Result	Execution time	Memory
362527		valerikk	Connecting Supertrees (IOI20_supertrees)	C++17	Compilation error	0 ms	0 KiB

supertrees

#include <bits/stdc++.h>

using namespace std;

struct dsu {
  vector<int> p;
   
  int get(int v) {
    return p[v] == v ? v : p[v] = get(p[v]);
  }

  bool uni(int v, int u) {
    v = get(v), u = get(u);
    p[v] = u;
    return v != u;
  }

  dsu() {}
  dsu(int n) {
    p = vector<int>(n);         
    for (int i = 0; i < n; i++) p[i] = i;
  }
};

int construct(vector<vector<int>> p) {
  int n = p.size();
  vector<vector<int>> g(n);
  for (int i = 0; i < n; i++) {
    if (p[i][i] != 1) return 0;
    for (int j = 0; j < i; j++) {
      if (p[i][j] != p[j][i]) return 0;
      if (p[i][j] == 3) return 0;
      g[i].push_back(j);
      g[j].push_back(i);
    }
  }    
  vector<bool> vis(n, false);
  vector<int> ind(n, -1);
  vector<int> comp;
  function<void(int)> dfs = [&](int v, int f) {
    comp.push_back(v);
    vis[v] = true;
    ind[v] = f;
    for (int u : g[v]) {
      if (!vis[u]) {
        dfs(u, f);
      }
    }
  };
  vector<pair<int, int>> ed;                
  for (int st = 0; st < n; st++) {
    if (!vis[st]) {
      comp = {};
      dfs(st, st);
      bool ok = true;
      bool cycle = false;            
      for (int v : comp) {
        for (int u : comp) {
          ok &= p[v][u] != 0; 
          cycle |= p[v][u] == 2;
        }
      }
      for (int v : comp) {
        for (int i = 0; i < n; i++) {
          if (ind[i] != st) ok &= p[v][i] == 0;
        }
      }     
      if (!ok) return 0; 
      int sz = comp.size();
      dsu d(n);             
      for (int v : comp) {
        for (int u : comp) {
          if (p[v][u] == 1) d.uni(v, u);
        }
      }   
      for (int v : comp) {
        for (int u : comp) {
          int kek = 1 + (d.get(v) != d.get(u));
          ok &= kek == p[v][u];  
        }
      }
      if (!ok) return 0;
      if (cycle) {
        vector<int> arr;
        for (int v : comp) arr.push_back(d.get(v));
        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(), arr.end()), arr.end());
        if (arr.size() < 3) return 0;
        for (int i = 0; i < arr.size(); i++) ed.push_back({arr[i], arr[(i + 1) % arr.size()]});
        vector<vector<int>> have(arr.size());
        for (int v : comp) {
          have[lower_bound(arr.begin(), arr.end(), d.get(v)) - arr.begin()].push_back(v);
        }                 
        for (int i = 0; i < arr.size(); i++) {
          for (int j = 0; j + 1 < have[i].size(); j++) {
            ed.push_back({have[i][j], have[i][j + 1]});
          }
        }

      } else {
        for (int i = 0; i + 1 < comp.size(); i++) ed.push_back({comp[i], comp[i + 1]});
      }
    }
  }                
  for (auto e : ed) build(e.first, e.second);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In lambda function:
supertrees.cpp:46:17: error: no match for call to '(std::function<void(int)>) (int&, int&)'
   46 |         dfs(u, f);
      |                 ^
In file included from /usr/include/c++/9/functional:59,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from supertrees.cpp:1:
/usr/include/c++/9/bits/std_function.h:683:5: note: candidate: '_Res std::function<_Res(_ArgTypes ...)>::operator()(_ArgTypes ...) const [with _Res = void; _ArgTypes = {int}]'
  683 |     function<_Res(_ArgTypes...)>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/std_function.h:683:5: note:   candidate expects 1 argument, 2 provided
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:49:3: error: conversion from 'construct(std::vector<std::vector<int> >)::<lambda(int, int)>' to non-scalar type 'std::function<void(int)>' requested
   49 |   };
      |   ^
supertrees.cpp:54:17: error: no match for call to '(std::function<void(int)>) (int&, int&)'
   54 |       dfs(st, st);
      |                 ^
In file included from /usr/include/c++/9/functional:59,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from supertrees.cpp:1:
/usr/include/c++/9/bits/std_function.h:683:5: note: candidate: '_Res std::function<_Res(_ArgTypes ...)>::operator()(_ArgTypes ...) const [with _Res = void; _ArgTypes = {int}]'
  683 |     function<_Res(_ArgTypes...)>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/std_function.h:683:5: note:   candidate expects 1 argument, 2 provided
supertrees.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i = 0; i < arr.size(); i++) ed.push_back({arr[i], arr[(i + 1) % arr.size()]});
      |                         ~~^~~~~~~~~~~~
supertrees.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int i = 0; i < arr.size(); i++) {
      |                         ~~^~~~~~~~~~~~
supertrees.cpp:95:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |           for (int j = 0; j + 1 < have[i].size(); j++) {
      |                           ~~~~~~^~~~~~~~~~~~~~~~
supertrees.cpp:101:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int i = 0; i + 1 < comp.size(); i++) ed.push_back({comp[i], comp[i + 1]});
      |                         ~~~~~~^~~~~~~~~~~~~
supertrees.cpp:69:11: warning: unused variable 'sz' [-Wunused-variable]
   69 |       int sz = comp.size();
      |           ^~
supertrees.cpp:105:21: error: 'build' was not declared in this scope
  105 |   for (auto e : ed) build(e.first, e.second);
      |                     ^~~~~