oj.uz

Submission #202626

# Submission time Handle Problem Language Result Execution time Memory
202626 2020-02-17T11:28:05 Z anonymous Job Scheduling (IOI19_job) C++14
5 / 100
 203 ms 79864 KB 
#include "job.h"
#include <vector>
#include<set>
#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];
multiset<Job, CompareClass> Order[MAXN];

int dfs(int u) {
    big[u]=u;
    for (auto v: chd[u]) {
        int p = dfs(v);
        while (Order[p].size()) {
            Job f = *Order[p].begin();
            if (f.wt*D[u] >= f.t*U[u]) {
                ans-=f.t*U[u];
                U[u]+=f.wt, D[u]+=f.t;
                Order[p].erase(Order[p].begin());
            } else {
                break;
            }
        }
    }
    Order[big[u]].insert(Job {U[u], D[u]});
    for (auto v: chd[u]) {
        if (Order[big[v]].size() > Order[big[u]].size()) {
            swap(big[u], big[v]);
        }
        for (Job j: Order[big[v]]) {
            Order[big[u]].insert(j);
        }
    }
    return(big[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;
	int ptr = dfs(0);
	for (Job j: Order[ptr]) {
        time+=j.t;
        ans+=j.wt*time;
	}
	return(ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21496 KB Output is correct
2 Correct 18 ms 21496 KB Output is correct
3 Correct 18 ms 21496 KB Output is correct
4 Correct 19 ms 21880 KB Output is correct
5 Correct 67 ms 34116 KB Output is correct
6 Correct 101 ms 46584 KB Output is correct
7 Correct 145 ms 58872 KB Output is correct
8 Correct 174 ms 71160 KB Output is correct
9 Correct 190 ms 71256 KB Output is correct
10 Correct 188 ms 71208 KB Output is correct
11 Correct 19 ms 21496 KB Output is correct
12 Correct 182 ms 71160 KB Output is correct
13 Correct 170 ms 60064 KB Output is correct
14 Correct 186 ms 71440 KB Output is correct
15 Correct 147 ms 58616 KB Output is correct
16 Correct 187 ms 71288 KB Output is correct
17 Correct 177 ms 71160 KB Output is correct
18 Correct 168 ms 71160 KB Output is correct
19 Correct 147 ms 58616 KB Output is correct
20 Correct 203 ms 79864 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21496 KB Output is correct
2 Correct 174 ms 63028 KB Output is correct
3 Incorrect 174 ms 63116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21496 KB Output is correct
2 Correct 18 ms 21496 KB Output is correct
3 Correct 18 ms 21496 KB Output is correct
4 Correct 19 ms 21880 KB Output is correct
5 Correct 67 ms 34116 KB Output is correct
6 Correct 101 ms 46584 KB Output is correct
7 Correct 145 ms 58872 KB Output is correct
8 Correct 174 ms 71160 KB Output is correct
9 Correct 190 ms 71256 KB Output is correct
10 Correct 188 ms 71208 KB Output is correct
11 Correct 19 ms 21496 KB Output is correct
12 Correct 182 ms 71160 KB Output is correct
13 Correct 170 ms 60064 KB Output is correct
14 Correct 186 ms 71440 KB Output is correct
15 Correct 147 ms 58616 KB Output is correct
16 Correct 187 ms 71288 KB Output is correct
17 Correct 177 ms 71160 KB Output is correct
18 Correct 168 ms 71160 KB Output is correct
19 Correct 147 ms 58616 KB Output is correct
20 Correct 203 ms 79864 KB Output is correct
21 Correct 18 ms 21496 KB Output is correct
22 Incorrect 19 ms 21496 KB Output isn't correct
23 Halted 0 ms 0 KB -