oj.uz

Submission #318934

# Submission time Handle Problem Language Result Execution time Memory
318934 2020-11-03T12:59:54 Z alextodoran Job Scheduling (IOI19_job) C++17
19 / 100
 301 ms 37020 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "job.h"

using namespace std;

typedef long long ll;

const int N_MAX = 200002;

int n;

struct Cost
{
    int d, u;
};

Cost cost[N_MAX];

int parent[N_MAX];

vector <int> sons[N_MAX];

bool operator < (const Cost &a, const Cost &b)
{
    return a.d * b.u < b.d * a.u;
}

struct Node
{
    int u;
    Cost c;
};

bool operator < (const Node &u, const Node &v)
{
    return make_pair(u.c, u.u) > make_pair(v.c, v.u);
}

set <Node> notJoined[N_MAX];

void mergeSets (set <Node>* in, set <Node>* from)
{
    bool swapped = false;
    if(in->size() < from->size())
    {
        swap(in, from);
        swapped = true;
    }
    while(from->empty() == false)
    {
        in->insert(*from->begin());
        from->erase(from->begin());
    }
    if(swapped == true)
        swap(in, from);
}

bool isRoot[N_MAX];

void dfs (int u)
{
    for(int v : sons[u])
    {
        dfs(v);
        notJoined[u].insert(Node{v, cost[v]});
    }
    isRoot[u] = true;
    while(notJoined[u].empty() == false)
    {
        int v = notJoined[u].begin()->u;
        if(!(cost[v] < cost[u]))
            break;
        notJoined[u].erase(notJoined[u].begin());
        isRoot[v] = false;
        cost[u].d += cost[v].d;
        cost[u].u += cost[v].u;
        mergeSets(&notJoined[u], &notJoined[v]);
    }
}

int order[N_MAX];

int curr;

bool seen[N_MAX];

void solveOne (int u)
{
    seen[u] = true;
    order[++curr] = u;
    vector <pair <Cost, int> > aux;
    for(int v : sons[u])
        if(isRoot[v] == false)
            aux.push_back(make_pair(cost[v], v));
    sort(aux.begin(), aux.end());
    for(pair <Cost, int> p : aux)
        solveOne(p.second);
}

void solveAll (int u)
{
    solveOne(u);
    vector <int> aux;
    while(notJoined[u].empty() == false)
    {
        int v = notJoined[u].begin()->u;
        notJoined[u].erase(notJoined[u].begin());
        aux.push_back(v);
    }
    reverse(aux.begin(), aux.end());
    for(int v : aux)
        solveAll(v);
}

ll scheduling_cost (vector <int> p, vector <int> u, vector <int> d)
{
    n = p.size();
    for(int i = 1; i <= n; i++)
    {
        parent[i] = p[i - 1] + 1;
        cost[i] = Cost{d[i - 1], u[i - 1]};
    }
    for(int i = 2; i <= n; i++)
        sons[parent[i]].push_back(i);
    dfs(1);
    solveAll(1);
    int currTime = 0;
    ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        assert(seen[i] == true);
        int j = order[i];
        currTime += d[j - 1];
        ans += 1LL * currTime * u[j - 1];
    }
    return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Runtime error 29 ms 29152 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 11 ms 14444 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 276 ms 36948 KB Output is correct
5 Correct 283 ms 36824 KB Output is correct
6 Correct 284 ms 36892 KB Output is correct
7 Correct 277 ms 36976 KB Output is correct
8 Correct 276 ms 36824 KB Output is correct
9 Correct 279 ms 36956 KB Output is correct
10 Correct 301 ms 36824 KB Output is correct
11 Correct 288 ms 36828 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 11 ms 14568 KB Output is correct
5 Correct 18 ms 15596 KB Output is correct
6 Correct 261 ms 36952 KB Output is correct
7 Correct 263 ms 36828 KB Output is correct
8 Correct 263 ms 36820 KB Output is correct
9 Correct 273 ms 36824 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 11 ms 14572 KB Output is correct
12 Correct 16 ms 15468 KB Output is correct
13 Correct 18 ms 15596 KB Output is correct
14 Correct 262 ms 36828 KB Output is correct
15 Correct 262 ms 36952 KB Output is correct
16 Correct 272 ms 36824 KB Output is correct
17 Correct 270 ms 36828 KB Output is correct
18 Correct 266 ms 36824 KB Output is correct
19 Correct 256 ms 36952 KB Output is correct
20 Correct 261 ms 36824 KB Output is correct
21 Correct 268 ms 36820 KB Output is correct
22 Correct 264 ms 37020 KB Output is correct
23 Correct 278 ms 36824 KB Output is correct
24 Correct 276 ms 36824 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 29036 KB Execution killed with signal 6 (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 29 ms 29156 KB Execution killed with signal 6 (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 Correct 10 ms 14444 KB Output is correct
2 Runtime error 29 ms 29152 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -