oj.uz

Submission #202712

# Submission time Handle Problem Language Result Execution time Memory
202712 2020-02-17T20:48:04 Z anonymous Job Scheduling (IOI19_job) C++14
0 / 100
 35 ms 33860 KB 
#include "job.h"
#include <vector>
#include<queue>
#include<iostream>
#define LL long long
#define MAXN 300005
using namespace std;
struct Job {LL wt, t;};
class CompareClass {
public:
    bool operator() (Job a, Job b) {
        return(a.wt*b.t < a.t*b.wt); //wt, time
    }
};
int N, big[MAXN];
LL U[MAXN], D[MAXN], ans; //cost, time
vector<int> chd[MAXN];
priority_queue<Job, vector<Job>, CompareClass> Order[MAXN];

void dfs(int u) {
    big[u]=u;
    for (auto v: chd[u]) {
        dfs(v);
        if (Order[big[v]].size() > Order[big[u]].size()) {swap(big[u], big[v]);}
        while (Order[big[u]].size()) {
            Order[big[u]].push(Order[big[v]].top());
            Order[big[v]].pop();
        }
    }
    while (Order[big[u]].size()) {
            Job f = Order[big[u]].top();
            if (f.wt*D[u] >= f.t*U[u]) {
                ans-=f.t*U[u];
                U[u]+=f.wt, D[u]+=f.t;
                Order[big[u]].pop();
            } else {
                break;
            }
    }
    Order[big[u]].push(Job {U[u], D[u]});
}
LL scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
	N=p.size();
	for(int i=0; i<N; i++) {
        if (i) {chd[p[i]].push_back(i);}
        U[i]=u[i], D[i]=d[i];
	}
	LL time=0;
	dfs(0);
	while (Order[big[0]].size()) {
	    Job j = Order[big[0]].top();
	    Order[big[0]].pop();
        time+=j.t;
        ans+=j.wt*time;
	}
	return(ans);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 33784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 33784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 33860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 33784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 33784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 33784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -