Submission #802818

#	Time	Username	Problem	Language	Result	Execution time	Memory
802818		Ahmed57	Job Scheduling (IOI19_job)	C++17	5 / 100	80 ms	25760 KiB

job

#include<bits/stdc++.h>

using namespace std;
long long D[200001],U[200001];
vector<int> adj[200001];
bool comp(int a,int b){
     return (D[a]*U[b])<(D[b]*U[a]);
}
long long scheduling_cost(vector<int> p,vector<int> u,vector<int> d){
    int n = p.size();
    int real[n];
    long long nxt[n];
    U[0] = u[0] , D[0] = d[0];
    real[0] = 1;nxt[0] = -1;
    for(int i = 1;i<n;i++){
        real[i] = 1;
        nxt[i] = -1;
        U[i] = u[i];
        D[i] = d[i];
        adj[p[i]].push_back(i);
    }
    for(int i = n-1;i>=0;i--){
        while(adj[i].size()){
            int x = -1;
            if(comp(adj[i].back(),i)){
                x = adj[i].back();
            }
            adj[i].pop_back();
            if(x==-1)continue;
            real[x] = 0;
            nxt[i] = x;
            D[i]+=D[x];
            U[i]+=U[x];
            if(adj[i].size()<adj[x].size())swap(adj[i],adj[x]);
            while(adj[x].size()){
                adj[i].push_back(adj[x].back());adj[x].pop_back();
            }
        }
    }
    vector<int> ans;
    for(int i = 0;i<n;i++){
        if(real[i]){
            ans.push_back(i);
        }
    }
    sort(ans.begin(),ans.end());
    long long all = 0 , cur = 0;
    for(int i = 0;i<ans.size();i++){
        int lol = ans[i];
        while(lol!=-1){
        cur+=d[lol];
        all+=cur*u[lol];
        lol = nxt[lol];
        }
    }
    return all;
}
/*
int main(){
    cout<<scheduling_cost({-1,0,0},{5,2,5},{3,4,1});
}*/

Compilation message (stderr)

job.cpp: In function 'long long int scheduling_cost(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0;i<ans.size();i++){
      |                   ~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 37