Submission #210876

#	Time	Username	Problem	Language	Result	Execution time	Memory
210876		briansu	Job Scheduling (IOI19_job)	C++14	100 / 100	365 ms	35076 KiB

job

    #include "job.h"
    #include <vector>
    #include <bits/stdc++.h>
     
    using namespace std;
     
    typedef long long ll;
     
    vector<int> ord, t;
    vector<vector<int>> v;
     
    struct frac
    {
        int x, y, id;
    };
     
    struct cmp
    {
        bool operator () (frac a, frac b)
        {
            return (ll) a.x * b.y > (ll) b.x * a.y;
        }
    };
     
    void dfs(int node)
    {
        ord.push_back(node);
        for(auto it : v[node])
            dfs(it);
    }
     
    int boss(int x)
    {
        if(x == t[x]) return x;
        return t[x] = boss(t[x]);
    }
     
    ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d)
    {
        priority_queue<frac, vector<frac>, cmp> heap;
     
        vector<int> U, D;
        U = u;
        D = d;
     
        int i, n = p.size();
     
        for(i=1; i<n; ++i)
            heap.push({D[i], U[i], i});
     
        t.resize(n);
     
        for(i=0; i<n; ++i)
            t[i] = i;
     
        v.resize(n);
     
        while(heap.size())
        {
            auto el = heap.top();
            heap.pop();
     
            if(make_pair(D[el.id], U[el.id]) != make_pair(el.x, el.y)) continue;
     
            int father = boss(p[el.id]);
            t[el.id] = father;
     
            D[father] += D[el.id];
            U[father] += U[el.id];
     
            v[father].push_back(el.id);
     
            if(father)
                heap.push({D[father], U[father], father});
        }
     
        dfs(0);
     
        ll sum = 0, ans = 0;
     
        for(auto it : ord)
        {
            sum += d[it];
            ans += sum * u[it];
        }
     
    	return ans;
    }

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