oj.uz

Submission #802891

# Submission time Handle Problem Language Result Execution time Memory
802891 2023-08-02T15:39:47 Z Ahmed57 Job Scheduling (IOI19_job) C++17
0 / 100
 6 ms 6484 KB 
#include<bits/stdc++.h>

using namespace std;
long long D[200001],U[200001];
int nxt[200001],nick_name[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];
vector<int> ans;
void dfs(int u) {
	ans.push_back(u);
	for(;adj[u].size();adj[u].pop())dfs(adj[u].top());
}
long long scheduling_cost(vector<int> p,vector<int> u,vector<int> d){
    int n = p.size();
    iota(nick_name,nick_name+n,0);
    memset(nxt,-1,n*4);
    for(int i = 1;i<n;i++){
        adj[p[i]].push(i);
    }
    for(int i = n-1;i>=0;i--){
        while(adj[i].size()){
            int x = -1;
            if(cmp()(i,adj[i].top())){
                x = adj[i].top();
            }else break;
            adj[i].pop();
            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();
            }
        }
    }
    dfs(0);
    sort(ans.begin(),ans.end(),cmp());
    long long all = 0 , cur = 0;
    for(int i = ans.size()-1;i>=0;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});
}*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 37.0

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