Submission #866435

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
866435	2023-10-26T07:21:53 Z	SorahISA	Job Scheduling (IOI19_job)	C++17	Compilation error	0 ms	0 KB

job

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

using int64 = long long;

struct Job {
    int64 u, d, id;
    bool operator < (const Job &rhs) const {
        return d * rhs.u < rhs.d * u;
    }
};

int64 scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
    int N = p.size();
    vector<vector<int>> ch(N);
    for (int i = 1; i < N; ++i) ch[p[i]].emplace_back(i);
    
    multiset<Job> jobs;
    for (int i = 0; i < N; ++i) jobs.emplace(u[i], d[i], i);
    
    int64 tim = 0, ans = 0;
    while (jobs.size()) {
        
        Job job = *begin(jobs);
        jobs.erase(begin(jobs));
        
        // cerr << "(" << job.u << ", " << job.d << ", " << job.id << ")\n";
        if (u[job.id] != job.u or d[job.id] != job.d) continue;
        // cerr << "(" << job.u << ", " << job.d << ", " << job.id << ")\n";
        
        if (p[job.id] == -1) {
            ans += job.u * (tim += job.d);
            for (int x : ch[job.id]) p[x] = -1;
        }
        else {
            ans -= u[p[job.id]] * d[job.id];
            int new_u = u[p[job.id]] + u[job.id];
            int new_d = d[p[job.id]] + d[job.id];
            
            // if (ch[p[job.id]].size() <= ch[job.id].size()) {
            //     u[job.id] = new_u, d[job.id] = new_d;
            //     for (int x : ch[p[job.id]]) {if (x != job.id) ch[job.id].emplace_back(x), p[x] = job.id;}
            //     ch[p[job.id]].clear();
            //     if (p[p[job.id]] != -1) ch[p[p[job.id]]].emplace_back(job.id);
            //     p[job.id] = p[p[job.id]];
            //     jobs.emplace(u[job.id], d[job.id], job.id);
            // }
            // else {
                u[p[job.id]] = new_u, d[p[job.id]] = new_d;
                for (int x : ch[job.id]) ch[p[job.id]].emplace_back(x), p[x] = p[job.id];
                ch[job.id].clear();
                jobs.emplace(u[p[job.id]], d[p[job.id]], p[job.id]);
            // }
        }
    }
    
    return ans;
}

Compilation message

In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/vector:64,
                 from job.h:5,
                 from job.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = Job; _Args = {int&, int&, int&}; _Tp = std::_Rb_tree_node<Job>]':
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_Tp1> >::construct(std::allocator_traits<std::allocator<_Tp1> >::allocator_type&, _Up*, _Args&& ...) [with _Up = Job; _Args = {int&, int&, int&}; _Tp = std::_Rb_tree_node<Job>; std::allocator_traits<std::allocator<_Tp1> >::allocator_type = std::allocator<std::_Rb_tree_node<Job> >]'
/usr/include/c++/10/bits/stl_tree.h:618:32:   required from 'void std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_construct_node(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type, _Args&& ...) [with _Args = {int&, int&, int&}; _Key = Job; _Val = Job; _KeyOfValue = std::_Identity<Job>; _Compare = std::less<Job>; _Alloc = std::allocator<Job>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<Job>*]'
/usr/include/c++/10/bits/stl_tree.h:635:21:   required from 'std::_Rb_tree_node<_Val>* std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_create_node(_Args&& ...) [with _Args = {int&, int&, int&}; _Key = Job; _Val = Job; _KeyOfValue = std::_Identity<Job>; _Compare = std::less<Job>; _Alloc = std::allocator<Job>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<Job>*]'
/usr/include/c++/10/bits/stl_tree.h:2440:33:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_emplace_equal(_Args&& ...) [with _Args = {int&, int&, int&}; _Key = Job; _Val = Job; _KeyOfValue = std::_Identity<Job>; _Compare = std::less<Job>; _Alloc = std::allocator<Job>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<Job, Job, std::_Identity<Job>, std::less<Job>, std::allocator<Job> >::iterator]'
/usr/include/c++/10/bits/stl_multiset.h:458:32:   required from 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::emplace(_Args&& ...) [with _Args = {int&, int&, int&}; _Key = Job; _Compare = std::less<Job>; _Alloc = std::allocator<Job>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Job, Job, std::_Identity<Job>, std::less<Job>, std::allocator<Job> >::const_iterator]'
job.cpp:20:59:   required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: new initializer expression list treated as compound expression [-fpermissive]
  150 |  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'Job::Job(int&)'
job.cpp:7:8: note: candidate: 'Job::Job()'
    7 | struct Job {
      |        ^~~
job.cpp:7:8: note:   candidate expects 0 arguments, 1 provided
job.cpp:7:8: note: candidate: 'constexpr Job::Job(const Job&)'
job.cpp:7:8: note:   no known conversion for argument 1 from 'int' to 'const Job&'
job.cpp:7:8: note: candidate: 'constexpr Job::Job(Job&&)'
job.cpp:7:8: note:   no known conversion for argument 1 from 'int' to 'Job&&'