| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 210949 | 2020-03-19T03:24:07 Z | Kevin_Zhang_TW | Job Scheduling (IOI19_job) | C++17 | Compilation error |
0 ms | 0 KB |
#include "job.h"
#include <bits/extc++.h>
#include <vector>
#define pb emplace_back
const int maxn = 200010;
using ll = long long;
using namespace std;
int deg[maxn], togo[maxn], tl, n;
ll res;
vector<int> edge[maxn];
vector<ll> p, u, d, sorted[maxn];
struct cmp {
bool operator()(int a, int b) const {
return d[a] * u[b] > d[b] * u[a];
}
};
void sub_merge(int a, int b) {
res -= (ll)d[b] * u[a];
d[a] += d[b];
u[a] += u[b];
}
//__gnu_pbds::priority_queue<int, cmp> pq[maxn];
void get_ans() {
for (int i = 0;i < n;++i) {
int now = togo[i];
//cerr << "now " << now << '\n';
assert(now || i == n-1);
for (int u : edge[now]) {
if (sorted[u].size() > sorted[now].size()) swap(sorted[u], sorted[now]);
int a = sorted[now].size();
sorted[now].insert(sorted[now].begin(), sorted[u].begin(), sorted[u].end());
inplace_merge(sorted[now].begin(), sorted[now].begin()+a, sorted[now].end(), cmp());
}
while (sorted[now].size() && cmp()(now, sorted[now].back())) {
sub_merge(now, sorted[now].back());
sorted[now].pop_back();
}
sorted[now].pb(now);
}
auto &v = sorted[0];
ll t = 0;
auto dojob = [&](int a) {
//cerr << "dojob " << a << ' ' << "d, u : " << d[a] << ' ' << u[a] << '\n';
t += d[a];
res += t * u[a];
};
while (v.size()) {
dojob(v.back());
v.pop_back();
}
}
//
//void dfs(int now) {
// for (int u : edge[i]) dfs(u);
// sort(edge[now].begin(), edge[now].end(), cmp());
// vector<int> down;
// while (edge[now].size() && cmp(now, edge[now].back())) {
// for (int u : merge(now, edge[now].back()))
// down.pb(u);
// edge[now].pop_back();
// }
// for (int u : down) edge[now].pb(u);
//}
//
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
n = p.size();
for (int i = 1;i < n;++i) edge[p[i]].pb(i);
for (int i = 1;i < n;++i) ++deg[ p[i] ];
for (int i = 0;i < n;++i) if (deg[i] == 0)
togo[tl++] = i;
for (int i = 0;i < n;++i) {
int now = togo[i];
if (now == 0) break;
if ( --deg[ p[now] ] == 0) togo[tl++] = p[now];
}
swap(p, ::p), swap(u, ::u), swap(d, ::d);
get_ans();
return res;
}
Compilation message
job.cpp: In function 'long long int scheduling_cost(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:77:13: error: no matching function for call to 'swap(std::vector<int>&, std::vector<long long int>&)'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/complex:45:0,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/sstream:796:5: note: candidate: template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(std::__cxx11::basic_stringbuf<_CharT, _Traits, _Alloc>&, std::__cxx11::basic_stringbuf<_CharT, _Traits, _Alloc>&)
swap(basic_stringbuf<_CharT, _Traits, _Allocator>& __x,
^~~~
/usr/include/c++/7/sstream:796:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::__cxx11::basic_stringbuf<_CharT, _Traits, _Alloc>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/complex:45:0,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/sstream:803:5: note: candidate: template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(std::__cxx11::basic_istringstream<_CharT, _Traits, _Allocator>&, std::__cxx11::basic_istringstream<_CharT, _Traits, _Allocator>&)
swap(basic_istringstream<_CharT, _Traits, _Allocator>& __x,
^~~~
/usr/include/c++/7/sstream:803:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::__cxx11::basic_istringstream<_CharT, _Traits, _Allocator>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/complex:45:0,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/sstream:810:5: note: candidate: template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(std::__cxx11::basic_ostringstream<_CharT, _Traits, _Allocator>&, std::__cxx11::basic_ostringstream<_CharT, _Traits, _Allocator>&)
swap(basic_ostringstream<_CharT, _Traits, _Allocator>& __x,
^~~~
/usr/include/c++/7/sstream:810:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::__cxx11::basic_ostringstream<_CharT, _Traits, _Allocator>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/complex:45:0,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/sstream:817:5: note: candidate: template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(std::__cxx11::basic_stringstream<_CharT, _Traits, _Allocator>&, std::__cxx11::basic_stringstream<_CharT, _Traits, _Allocator>&)
swap(basic_stringstream<_CharT, _Traits, _Allocator>& __x,
^~~~
/usr/include/c++/7/sstream:817:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::__cxx11::basic_stringstream<_CharT, _Traits, _Allocator>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/regex:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/bits/regex.h:805:5: note: candidate: template<class _Ch_type, class _Rx_traits> void std::__cxx11::swap(std::__cxx11::basic_regex<_Ch_type, _Rx_traits>&, std::__cxx11::basic_regex<_Ch_type, _Rx_traits>&)
swap(basic_regex<_Ch_type, _Rx_traits>& __lhs,
^~~~
/usr/include/c++/7/bits/regex.h:805:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::__cxx11::basic_regex<_Ch_type, _Rx_traits>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/regex:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/bits/regex.h:1958:5: note: candidate: template<class _Bi_iter, class _Alloc> void std::__cxx11::swap(std::__cxx11::match_results<_BiIter, _Alloc>&, std::__cxx11::match_results<_BiIter, _Alloc>&)
swap(match_results<_Bi_iter, _Alloc>& __lhs,
^~~~
/usr/include/c++/7/bits/regex.h:1958:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::__cxx11::match_results<_BiIter, _Alloc>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/bits/stl_pair.h:59:0,
from /usr/include/c++/7/bits/stl_algobase.h:64,
from /usr/include/c++/7/vector:60,
from job.h:5,
from job.cpp:1:
/usr/include/c++/7/bits/move.h:187:5: note: candidate: template<class _Tp> typename std::enable_if<std::__and_<std::__not_<std::__is_tuple_like<_Tp> >, std::is_move_constructible<_Tp>, std::is_move_assignable<_Tp> >::value>::type std::swap(_Tp&, _Tp&)
swap(_Tp& __a, _Tp& __b)
^~~~
/usr/include/c++/7/bits/move.h:187:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: deduced conflicting types for parameter '_Tp' ('std::vector<int>' and 'std::vector<long long int>')
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/bits/stl_pair.h:59:0,
from /usr/include/c++/7/bits/stl_algobase.h:64,
from /usr/include/c++/7/vector:60,
from job.h:5,
from job.cpp:1:
/usr/include/c++/7/bits/move.h:210:5: note: candidate: template<class _Tp, long unsigned int _Nm> typename std::enable_if<std::__is_swappable<_Tp>::value>::type std::swap(_Tp (&)[_Nm], _Tp (&)[_Nm])
swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
^~~~
/usr/include/c++/7/bits/move.h:210:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: mismatched types '_Tp [_Nm]' and 'std::vector<int>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/bits/stl_algobase.h:64:0,
from /usr/include/c++/7/vector:60,
from job.h:5,
from job.cpp:1:
/usr/include/c++/7/bits/stl_pair.h:490:5: note: candidate: template<class _T1, class _T2> typename std::enable_if<std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value>::type std::swap(std::pair<_T1, _T2>&, std::pair<_T1, _T2>&)
swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
^~~~
/usr/include/c++/7/bits/stl_pair.h:490:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::pair<_T1, _T2>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/bits/stl_algobase.h:64:0,
from /usr/include/c++/7/vector:60,
from job.h:5,
from job.cpp:1:
/usr/include/c++/7/bits/stl_pair.h:498:5: note: candidate: template<class _T1, class _T2> typename std::enable_if<(! std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value)>::type std::swap(std::pair<_T1, _T2>&, std::pair<_T1, _T2>&) <deleted>
swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
^~~~
/usr/include/c++/7/bits/stl_pair.h:498:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::pair<_T1, _T2>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/vector:64:0,
from job.h:5,
from job.cpp:1:
/usr/include/c++/7/bits/stl_vector.h:1644:5: note: candidate: template<class _Tp, class _Alloc> void std::swap(std::vector<_Tp, _Alloc>&, std::vector<_Tp, _Alloc>&)
swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
^~~~
/usr/include/c++/7/bits/stl_vector.h:1644:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: deduced conflicting types for parameter '_Tp' ('int' and 'long long int')
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/vector:65:0,
from job.h:5,
from job.cpp:1:
/usr/include/c++/7/bits/stl_bvector.h:112:3: note: candidate: void std::swap(std::_Bit_reference, std::_Bit_reference)
swap(_Bit_reference __x, _Bit_reference __y) noexcept
^~~~
/usr/include/c++/7/bits/stl_bvector.h:112:3: note: no known conversion for argument 1 from 'std::vector<int>' to 'std::_Bit_reference'
/usr/include/c++/7/bits/stl_bvector.h:120:3: note: candidate: void std::swap(std::_Bit_reference, bool&)
swap(_Bit_reference __x, bool& __y) noexcept
^~~~
/usr/include/c++/7/bits/stl_bvector.h:120:3: note: no known conversion for argument 1 from 'std::vector<int>' to 'std::_Bit_reference'
/usr/include/c++/7/bits/stl_bvector.h:128:3: note: candidate: void std::swap(bool&, std::_Bit_reference)
swap(bool& __x, _Bit_reference __y) noexcept
^~~~
/usr/include/c++/7/bits/stl_bvector.h:128:3: note: no known conversion for argument 1 from 'std::vector<int>' to 'bool&'
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/bits/basic_string.h:6234:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> void std::swap(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
^~~~
/usr/include/c++/7/bits/basic_string.h:6234:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/deque:64:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:68,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/bits/stl_deque.h:2312:5: note: candidate: template<class _Tp, class _Alloc> void std::swap(std::deque<_Tp, _Alloc>&, std::deque<_Tp, _Alloc>&)
swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
^~~~
/usr/include/c++/7/bits/stl_deque.h:2312:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::deque<_Tp, _Alloc>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:70:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/fstream:1052:5: note: candidate: template<class _CharT, class _Traits> void std::swap(std::basic_filebuf<_CharT, _Traits>&, std::basic_filebuf<_CharT, _Traits>&)
swap(basic_filebuf<_CharT, _Traits>& __x,
^~~~
/usr/include/c++/7/fstream:1052:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::basic_filebuf<_CharT, _Traits>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:70:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/fstream:1059:5: note: candidate: template<class _CharT, class _Traits> void std::swap(std::basic_ifstream<_CharT, _Traits>&, std::basic_ifstream<_CharT, _Traits>&)
swap(basic_ifstream<_CharT, _Traits>& __x,
^~~~
/usr/include/c++/7/fstream:1059:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::basic_ifstream<_CharT, _Traits>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:70:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/fstream:1066:5: note: candidate: template<class _CharT, class _Traits> void std::swap(std::basic_ofstream<_CharT, _Traits>&, std::basic_ofstream<_CharT, _Traits>&)
swap(basic_ofstream<_CharT, _Traits>& __x,
^~~~
/usr/include/c++/7/fstream:1066:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::basic_ofstream<_CharT, _Traits>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:70:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/fstream:1073:5: note: candidate: template<class _CharT, class _Traits> void std::swap(std::basic_fstream<_CharT, _Traits>&, std::basic_fstream<_CharT, _Traits>&)
swap(basic_fstream<_CharT, _Traits>& __x,
^~~~
/usr/include/c++/7/fstream:1073:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::basic_fstream<_CharT, _Traits>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/tuple:39:0,
from /usr/include/c++/7/functional:54,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/array:294:5: note: candidate: template<class _Tp, long unsigned int _Nm> typename std::enable_if<typename std::__array_traits<_Tp, _Nm>::_Is_swappable:: value>::type std::swap(std::array<_Tp, _Nm>&, std::array<_Tp, _Nm>&)
swap(array<_Tp, _Nm>& __one, array<_Tp, _Nm>& __two)
^~~~
/usr/include/c++/7/array:294:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::array<_Tp, _Nm>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/tuple:39:0,
from /usr/include/c++/7/functional:54,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/array:302:5: note: candidate: template<class _Tp, long unsigned int _Nm> typename std::enable_if<(! typename std::__array_traits<_Tp, _Nm>::_Is_swappable:: value)>::type std::swap(std::array<_Tp, _Nm>&, std::array<_Tp, _Nm>&) <deleted>
swap(array<_Tp, _Nm>&, array<_Tp, _Nm>&) = delete;
^~~~
/usr/include/c++/7/array:302:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::array<_Tp, _Nm>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/functional:54:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/tuple:1602:5: note: candidate: template<class ... _Elements> typename std::enable_if<std::__and_<std::__is_swappable<_Elements>...>::value>::type std::swap(std::tuple<_Tps ...>&, std::tuple<_Tps ...>&)
swap(tuple<_Elements...>& __x, tuple<_Elements...>& __y)
^~~~
/usr/include/c++/7/tuple:1602:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::tuple<_Tps ...>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/functional:54:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/tuple:1609:5: note: candidate: template<class ... _Elements> typename std::enable_if<(! std::__and_<std::__is_swappable<_Elements>...>::value)>::type std::swap(std::tuple<_Tps ...>&, std::tuple<_Tps ...>&) <deleted>
swap(tuple<_Elements...>&, tuple<_Elements...>&) = delete;
^~~~
/usr/include/c++/7/tuple:1609:5: note: template argument deduction/substitution failed:
job.cpp:77:13: note: 'std::vector<int>' is not derived from 'std::tuple<_Tps ...>'
swap(p, ::p), swap(u, ::u), swap(d, ::d);
^
In file included from /usr/include/c++/7/functional:58:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:32,
from job.cpp:2:
/usr/include/c++/7/bits/std_function.h:803:5: note: candidate: template<class _Res, class ... _Args> void std::swap(std::function<_Res(_A