Submission #802869

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802869	2023-08-02T15:21:01 Z	Ahmed57	Job Scheduling (IOI19_job)	C++17	19 / 100	152 ms	25416 KB

#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();
            }
            adj[i].pop();
            if(x==-1)continue;
            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

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

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Incorrect	3 ms	6484 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6564 KB	Output is correct
2	Correct	3 ms	6568 KB	Output is correct
3	Correct	3 ms	6484 KB	Output is correct
4	Correct	129 ms	20808 KB	Output is correct
5	Correct	133 ms	20900 KB	Output is correct
6	Correct	129 ms	20896 KB	Output is correct
7	Correct	128 ms	20896 KB	Output is correct
8	Correct	129 ms	20900 KB	Output is correct
9	Correct	129 ms	20904 KB	Output is correct
10	Correct	134 ms	20908 KB	Output is correct
11	Correct	129 ms	20832 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6484 KB	Output is correct
2	Correct	3 ms	6484 KB	Output is correct
3	Correct	4 ms	6560 KB	Output is correct
4	Correct	4 ms	6612 KB	Output is correct
5	Correct	8 ms	7380 KB	Output is correct
6	Correct	136 ms	20796 KB	Output is correct
7	Correct	141 ms	21000 KB	Output is correct
8	Correct	135 ms	20820 KB	Output is correct
9	Correct	136 ms	20820 KB	Output is correct
10	Correct	3 ms	6568 KB	Output is correct
11	Correct	4 ms	6612 KB	Output is correct
12	Correct	7 ms	7252 KB	Output is correct
13	Correct	7 ms	7352 KB	Output is correct
14	Correct	140 ms	20880 KB	Output is correct
15	Correct	137 ms	20812 KB	Output is correct
16	Correct	137 ms	20888 KB	Output is correct
17	Correct	136 ms	20872 KB	Output is correct
18	Correct	139 ms	20796 KB	Output is correct
19	Correct	138 ms	20780 KB	Output is correct
20	Correct	137 ms	20888 KB	Output is correct
21	Correct	148 ms	20808 KB	Output is correct
22	Correct	152 ms	20888 KB	Output is correct
23	Correct	135 ms	20904 KB	Output is correct
24	Correct	138 ms	20796 KB	Output is correct