Submission #333217

#	Time	Username	Problem	Language	Result	Execution time	Memory
333217		limabeans	Railway (BOI17_railway)	C++17	Compilation error	0 ms	0 KiB

railway

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl










const int maxn = 1e5+10;



int n, m, k;
vector<pair<int,int>> g[maxn];
set<int> nodes[maxn];

const int LOG = 19;

int par[LOG+1][maxn];
int dep[maxn];


int lca(int u, int v) {
    if (dep[u]<dep[v]) swap(u,v);
    int dx = dep[u]-dep[v];
    for (int j=0; j<LOG; j++) {
	if (dx>>j&1) {
	    u = par[j][u];
	}
    }

    if (u==v) return v;

    for (int j=LOG-1; j>=0; j--) {
	if (par[j][u] != par[j][v]) {
	    u = par[j][u];
	    v = par[j][v];
	}
    }

    return par[0][u];
}

int tin[maxn];
int tout[maxn];
int cloc = 1;

void dfs(int at, int p) {
    for (int j=1; j<LOG; j++) {
	par[j][at] = par[j-1][par[j-1][at]];
    }

    tin[at] = cloc++;
    
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	dep[to]=1+dep[at];
	par[0][to] = at;
	dfs(to, at);
    }

    tout[at] = cloc++;
}


vector<int> add[maxn], sub[maxn];


vector<int> ans;

set<int> dfs2(int at, int p, int edId=0) {
    set<int> res;
    for (auto ed: g[at]) {
	int idx = ed.first;
	int to = ed.second;
	if (to==p) continue;
	auto ret = dfs2(to, at, idx);
	if (res.size() < ret.size()) {
	    swap(res, ret);
	}
	res.insert(ret.begin(), ret.end());
    }

    for (int x: add[at]) {
	res.insert(x);
    }

    for (int x: sub[at]) {
	res.erase(x);
    }

    if ((int)res.size() >= k && edId!=0) ans.push_back(edId);

    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m>>k;
    for (int i=1; i<n; i++) {
	int u,v; cin>>u>>v;
	g[u].push_back({i,v});
	g[v].push_back({i,u});
    }

    
    for (int i=1; i<=m; i++) {
	int t;
	cin>>t;
	while (t--) {
	    int x;
	    cin>>x;
	    nodes[i].insert(x);
	}
    }

    dfs(1,0);

    for (int i=1; i<=m; i++) {
	int top = *nodes[i].begin();
	for (int x: nodes[i]) {
	    add[x].insert(i);
	    top = lca(top, x);
	}
	sub[top].insert(i);
    }

    dfs2(1,0);


    cout<<ans.size()<<endl;
    for (int i: ans) cout<<i<<" ";
    cout<<endl;
    
    
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:132:21: error: no matching function for call to 'std::vector<int>::insert(int&)'
  132 |      add[x].insert(i);
      |                     ^
In file included from /usr/include/c++/9/vector:72,
                 from /usr/include/c++/9/functional:62,
                 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 railway.cpp:1:
/usr/include/c++/9/bits/vector.tcc:130:5: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*; std::vector<_Tp, _Alloc>::value_type = int]'
  130 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/vector.tcc:130:5: note:   candidate expects 2 arguments, 1 provided
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/functional:62,
                 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 railway.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:1290:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*; std::vector<_Tp, _Alloc>::value_type = int]'
 1290 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1290:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1307:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::initializer_list<_Tp>) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*]'
 1307 |       insert(const_iterator __position, initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1307:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1332:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = int]'
 1332 |       insert(const_iterator __position, size_type __n, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1332:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1376:2: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, _InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = int; _Alloc = std::allocator<int>]'
 1376 |  insert(const_iterator __position, _InputIterator __first,
      |  ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1376:2: note:   template argument deduction/substitution failed:
railway.cpp:132:21: note:   candidate expects 3 arguments, 1 provided
  132 |      add[x].insert(i);
      |                     ^
railway.cpp:135:19: error: no matching function for call to 'std::vector<int>::insert(int&)'
  135 |  sub[top].insert(i);
      |                   ^
In file included from /usr/include/c++/9/vector:72,
                 from /usr/include/c++/9/functional:62,
                 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 railway.cpp:1:
/usr/include/c++/9/bits/vector.tcc:130:5: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*; std::vector<_Tp, _Alloc>::value_type = int]'
  130 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/vector.tcc:130:5: note:   candidate expects 2 arguments, 1 provided
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/functional:62,
                 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 railway.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:1290:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*; std::vector<_Tp, _Alloc>::value_type = int]'
 1290 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1290:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1307:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::initializer_list<_Tp>) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*]'
 1307 |       insert(const_iterator __position, initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1307:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1332:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::_Vector_base<_Tp, _Alloc>::pointer = int*; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = int]'
 1332 |       insert(const_iterator __position, size_type __n, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1332:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/9/bits/stl_vector.h:1376:2: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, _InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = int; _Alloc = std::allocator<int>]'
 1376 |  insert(const_iterator __position, _InputIterator __first,
      |  ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:1376:2: note:   template argument deduction/substitution failed:
railway.cpp:135:19: note:   candidate expects 3 arguments, 1 provided
  135 |  sub[top].insert(i);
      |                   ^