Submission #1040548

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1040548	2024-08-01T07:11:33 Z	Requiem	Job Scheduling (IOI19_job)	C++17	Compilation error	0 ms	0 KB

job

#include <bits/stdc++.h>
#include "job.h"
#define ll long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
#define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;}
#define all(T) T.begin(),T.end()
using namespace std;
const double eps = 0.0000001;
const int mod = 1e9+7;
const int N = 200005;
const int MATRIX_SIZE = 64;
const int BLOCK=500;
ll n,w[N],t[N],p[N],ans,par[N],sz[N],tmp_w[N],tmp_t[N],trol;
vector <ll> G[N];
// bool ok(int pos1,int pos2){return w[pos1]*t[pos2]>w[pos2]*t[pos1];}
struct job{
    ll v,w,t;
};
struct cmp{
    bool operator () (job a,job b){if (a.w*b.t==b.w*a.t) return a.v<b.v;return a.w*b.t>b.w*a.t;}
};
set <job,cmp> luu[N];
list <ll> T[N];
ll get(ll x){
    if (x!=par[x]) return par[x]=get(par[x]);
    return x;
}
void noi(ll a,ll b){
    a=get(a);
    b=get(b);
    if (a==b) return;
    ll nguoi_giu_chia_khoa;
    if (T[a].size()>T[b].size()){
        nguoi_giu_chia_khoa=a;
        while (!T[b].empty()){
            T[a].push_back(T[b].front());
            T[b].pop_front();
        }
    }
    else{
        nguoi_giu_chia_khoa=b;
        while (!T[a].empty()){
            T[b].push_front(T[a].back());
            T[a].pop_back();
        }
    }
    if (sz[a]<sz[b]) swap(a,b);
    if (nguoi_giu_chia_khoa!=a)
        swap(T[b],T[a]);
    sz[a]+=sz[b];
    par[b]=a;
    w[a]+=w[b];
    t[a]+=t[b];
}
void DFS(ll v){
    // trol=v;
    for (auto child:G[v]){
        DFS(child);
        // trol=v;
        if (luu[child].size()>luu[v].size()) swap(luu[v],luu[child]);
        for (auto x:luu[child]) luu[v].insert(x);
    }
    job tam=*luu[v].begin();
    while (tam.w*t[get(v)]>w[get(v)]*tam.t){
        luu[v].erase(luu[v].begin());
        noi(v,tam.v);
        if (luu[v].empty()) break;
        tam=*luu[v].begin();
    }
    luu[v].insert({get(v),w[get(v)],t[get(v)]});
}
ll scheduling_cost(vector<int> _p, vector<int> _w, vector<int> _t) {
    n=_p.size();
 
    for (int i=1;i<=n;++i){
        p[i]=_p[i-1];
        G[p[i]].push_back(i);
        par[i]=i;
        sz[i]=1;
        T[i].push_back(i);
    }
    for (int i=1;i<=n;++i){
        w[i]=_w[i-1];
        tmp_w[i]=w[i];
    }
    for (int i=1;i<=n;++i){
        t[i]=_t[i-1];
        tmp_t[i]=t[i];
    }
    DFS(1);
    int d=0;
    for (auto sus:luu[1]){
        for (auto x:T[sus.v]){
            d+=tmp_t[x];
            ans+=tmp_w[x]*d;
        }
    }
    return ans;
}

Compilation message

In file included from /usr/include/c++/10/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from job.cpp:1:
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = job; _Val = job; _KeyOfValue = std::_Identity<job>; _Compare = cmp; _Alloc = std::allocator<job>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<job>*]':
/usr/include/c++/10/bits/stl_tree.h:2101:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = job; _Val = job; _KeyOfValue = std::_Identity<job>; _Compare = cmp; _Alloc = std::allocator<job>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = job]'
/usr/include/c++/10/bits/stl_tree.h:2154:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = const job&; _Key = job; _Val = job; _KeyOfValue = std::_Identity<job>; _Compare = cmp; _Alloc = std::allocator<job>]'
/usr/include/c++/10/bits/stl_set.h:512:25:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = job; _Compare = cmp; _Alloc = std::allocator<job>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<job, job, std::_Identity<job>, cmp, std::allocator<job> >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = job]'
job.cpp:66:48:   required from here
/usr/include/c++/10/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
  780 |        is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~