Submission #474348

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474348	2021-09-18T04:05:51 Z	Lam_lai_cuoc_doi	Job Scheduling (IOI19_job)	C++17	7 / 100	289 ms	15208 KB

#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;
constexpr ld eps = 1e-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 (ld)a * 1.0 / b < (ld)x.a * 1.0 / x.b;
    }
    bool operator==(const Fraction &x) const
    {
        return abs((ld)a * 1.0 / b - (ld)x.a * 1.0 / x.b) < eps;
    }
};

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 -= 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

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
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	972 KB	Output is correct
2	Correct	1 ms	972 KB	Output is correct
3	Incorrect	1 ms	972 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	972 KB	Output is correct
2	Correct	1 ms	972 KB	Output is correct
3	Correct	1 ms	996 KB	Output is correct
4	Correct	151 ms	15164 KB	Output is correct
5	Correct	155 ms	15188 KB	Output is correct
6	Correct	155 ms	15168 KB	Output is correct
7	Correct	156 ms	15172 KB	Output is correct
8	Correct	152 ms	15152 KB	Output is correct
9	Correct	159 ms	15208 KB	Output is correct
10	Correct	168 ms	15132 KB	Output is correct
11	Correct	161 ms	15152 KB	Output is correct

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	972 KB	Output is correct
2	Correct	1 ms	972 KB	Output is correct
3	Correct	1 ms	972 KB	Output is correct
4	Correct	2 ms	1152 KB	Output is correct
5	Correct	7 ms	1936 KB	Output is correct
6	Incorrect	165 ms	15168 KB	Output isn't correct
7	Halted	0 ms	0 KB	-