oj.uz

Submission #314851

# Submission time Handle Problem Language Result Execution time Memory
314851 2020-10-21T13:30:34 Z blue Job Scheduling (IOI19_job) C++17
5 / 100
 130 ms 21368 KB 
#include "job.h"
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

struct job
{
    long long u;
    long long d;
    long long i;
    vector<long long> children;
};

bool operator < (job A, job B)
{
    if(A.u*B.d > B.u*A.d) return A.i < B.i;
    return A.u*B.d > B.u*A.d;
}

long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d)
{
    long long res = 0;
    long long n = p.size();

    job J[n];
    vector<long long> v;
    for(long long i = 0; i < n; i++)
    {
        J[i] = job{u[i], d[i], i, v};
        if(i > 0) J[p[i]].children.push_back(i);
    }

    long long t = 0;

    set<job> S;
    S.insert(J[0]);

    job j;

    while(!S.empty())
    {
        j = *S.begin();
        S.erase(S.begin());
        for(int k: j.children) S.insert(J[k]);
        t += j.d;
        res += t * j.u;
    }

	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 29 ms 5504 KB Output is correct
6 Correct 59 ms 10616 KB Output is correct
7 Correct 124 ms 15736 KB Output is correct
8 Correct 124 ms 20856 KB Output is correct
9 Correct 127 ms 20856 KB Output is correct
10 Correct 127 ms 20984 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 118 ms 21368 KB Output is correct
13 Correct 120 ms 21240 KB Output is correct
14 Correct 117 ms 20856 KB Output is correct
15 Correct 126 ms 20856 KB Output is correct
16 Correct 127 ms 20856 KB Output is correct
17 Correct 123 ms 20856 KB Output is correct
18 Correct 130 ms 20856 KB Output is correct
19 Correct 120 ms 20796 KB Output is correct
20 Correct 119 ms 20856 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 29 ms 5504 KB Output is correct
6 Correct 59 ms 10616 KB Output is correct
7 Correct 124 ms 15736 KB Output is correct
8 Correct 124 ms 20856 KB Output is correct
9 Correct 127 ms 20856 KB Output is correct
10 Correct 127 ms 20984 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 118 ms 21368 KB Output is correct
13 Correct 120 ms 21240 KB Output is correct
14 Correct 117 ms 20856 KB Output is correct
15 Correct 126 ms 20856 KB Output is correct
16 Correct 127 ms 20856 KB Output is correct
17 Correct 123 ms 20856 KB Output is correct
18 Correct 130 ms 20856 KB Output is correct
19 Correct 120 ms 20796 KB Output is correct
20 Correct 119 ms 20856 KB Output is correct
21 Incorrect 1 ms 256 KB Output isn't correct
22 Halted 0 ms 0 KB -