Submission #474399

#	Time	Username	Problem	Language	Result	Execution time	Memory
474399		Lam_lai_cuoc_doi	Job Scheduling (IOI19_job)	C++17	100 / 100	269 ms	17744 KiB

job

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
constexpr int Inf = 1e9 + 7;

struct dsu
{
    int par[N];
    dsu()
    {
        memset(par, -1, sizeof par);
    }
    int findpar(int v)
    {
        return par[v] < 0 ? v : par[v] = findpar(par[v]);
    }
} f;

struct Fraction
{
    ll a, b;
    Fraction(ll a = 0, ll b = 1) : a(a), b(b)
    {
        Normalize();
    }

    inline void Normalize()
    {
        ll v = __gcd(a, b);
        a /= v;
        b /= v;

        if (b < 0)
        {
            a = -a;
            b = -b;
        }
    }

    bool operator<(const Fraction &x) const
    {
        return a * x.b < b * x.a;
    }
    bool operator==(const Fraction &x) const
    {
        return a * x.b == b * x.a;
    }
};

ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d)
{
    int n = p.size();
    /*if (count(p.begin(), p.end(), 0) == n - 1)
    {

        vector<int> id(n);
        for (int i = 0; i < n; ++i)
            id[i] = i;
        sort(id.begin() + 1, id.end(), [&](const int &x, const int &y)
             { return d[x] * u[y] < d[y] * u[x]; });

        ll ans(0), time(0);
        for (int i = 0; i < n; ++i)
        {
            time += d[id[i]];
            //cout << id[i] << " " << time << "\n";
            ans += u[id[i]] * time;
        }
        return ans;
    }*/

    ll ans(0), time(0);
    vector<Fraction> ud(n);

    struct Tque
    {
        Fraction x;
        int v;
        Tque(Fraction x = Fraction(0, 1), ll v = 0) : x(x), v(v) {}

        bool operator<(const Tque &a) const
        {
            return x < a.x || (x == a.x && v > a.v);
        }
    };

    priority_queue<Tque> q;

    for (int i = 0; i < n; ++i)
    {
        ud[i] = Fraction(u[i], d[i]);
        q.emplace(ud[i], i);
    }

    while (!q.empty())
    {
        Tque c = q.top();
        q.pop();

        if (!(c.x == ud[c.v]))
            continue;

        if (p[c.v] == -1 || ud[f.findpar(p[c.v])] == Fraction(-1, 1))
        {
            time += d[c.v];
            ans += time * u[c.v];
            ud[c.v] = Fraction(-1, 1);
        }
        else
        {
            int v = f.findpar(p[c.v]);
            ans -= 1ll * u[v] * d[c.v];

            u[v] += u[c.v];
            d[v] += d[c.v];
            ud[v] = Fraction(u[v], d[v]);

            f.par[c.v] = v;

            q.emplace(ud[v], v);
        }
    }

    return ans;
}

void Read()
{
    int n;
    cin >> n;
    vector<int> p(n), d(n), u(n);
    for (int i = 0; i < n; ++i)
        cin >> p[i] >> u[i] >> d[i];

    cout << scheduling_cost(p, u, d);
}

void Solve()
{
}

Compilation message (stderr)

job.cpp: In function 'void read(T&)':
job.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

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