Submission #802861

#	Time	Username	Problem	Language	Result	Execution time	Memory
802861		Ahmed57	Job Scheduling (IOI19_job)	C++17	42 / 100	90 ms	27748 KiB

job

#include<bits/stdc++.h>

using namespace std;
long long D[200001],U[200001];
bool comp(int a,int b){
     return (D[a]*U[b])<(D[b]*U[a]);
}
struct cmp {
	bool operator()(const int &a, const int &b) {
		return (D[a]*U[b])>(D[b]*U[a]);
	}
};
priority_queue<int,vector<int>,cmp> adj[200001];
long long scheduling_cost(vector<int> p,vector<int> u,vector<int> d){
    int n = p.size();
    int real[n];
    long long nxt[n],nick_name[n];
    U[0] = u[0] , D[0] = d[0];
    real[0] = 1;nxt[0] = -1;
    nick_name[0] = 0;
    for(int i = 1;i<n;i++){
        nick_name[i] = i;
        real[i] = 1;
        nxt[i] = -1;
        U[i] = u[i];
        D[i] = d[i];
        adj[p[i]].push(i);
    }
    for(int i = n-1;i>=0;i--){
        while(adj[i].size()){
            int x = -1;
            if(comp(adj[i].top(),i)){
                x = adj[i].top();
            }else break;
            adj[i].pop();
            real[x] = 0;
            nxt[nick_name[i]] = x;
            nick_name[i] = nick_name[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(adj[x].top());adj[x].pop();
            }
        }
    }
    vector<int> ans;
    for(int i = 0;i<n;i++){
        if(real[i]){
            ans.push_back(i);
        }
    }
    sort(ans.begin(),ans.end(),comp);
    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:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0;i<ans.size();i++){
      |                   ~^~~~~~~~~~~

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