Submission #315766

#	Time	Username	Problem	Language	Result	Execution time	Memory
315766		tincamatei	Job Scheduling (IOI19_job)	C++14	100 / 100	324 ms	60792 KiB

job

#include "job.h"
#include <vector>
#include <set>
#include <cstdio>

const int MAX_N = 200000;

long long res;

std::vector<int> graph[MAX_N];

struct DSUNode {
    int nod, sd, su;

    DSUNode(int _nod, int _sd, int _su) {
        nod = _nod;
        sd = _sd;
        su = _su;
    }

    bool operator< (const DSUNode x) const {
        return (long long)sd * x.su < (long long)su * x.sd ||
            ((long long)sd * x.su == (long long)su * x.sd && nod < x.nod);
    }
};

struct DSU {
    int sd, su;
    std::set<DSUNode> extended_neighbours;
} dsu[MAX_N];

void join(int a, int b) {
    res = res + (long long)dsu[a].sd * dsu[b].su;
    dsu[a].sd += dsu[b].sd;
    dsu[a].su += dsu[b].su;
    
    dsu[a].extended_neighbours.erase({b, dsu[b].sd, dsu[b].su});
    if(dsu[a].extended_neighbours.size() < dsu[b].extended_neighbours.size())
        dsu[a].extended_neighbours.swap(dsu[b].extended_neighbours);
    
    for(auto it: dsu[b].extended_neighbours)
        dsu[a].extended_neighbours.insert(it);
    dsu[b].extended_neighbours.clear();
}

void dfs(int nod) {
    for(auto it: graph[nod]) {
        dfs(it);
        dsu[nod].extended_neighbours.insert({it, dsu[it].sd, dsu[it].su});
    }
    
    while(!dsu[nod].extended_neighbours.empty()
    && *dsu[nod].extended_neighbours.begin() < DSUNode(nod, dsu[nod].sd, dsu[nod].su))
        join(nod, dsu[nod].extended_neighbours.begin()->nod);
}

long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
    int n = u.size();
    for(int i = 0; i < n; ++i) {
        dsu[i] = {d[i], u[i]};
        res = res + (long long)u[i] * d[i];
    }
    for(int i = 1; i < n; ++i)
        graph[p[i]].push_back(i);
    
    dfs(0);
    
    while(!dsu[0].extended_neighbours.empty())
        join(0, dsu[0].extended_neighbours.begin()->nod);

    return res;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 37 / 37