Submission #1095777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095777		Requiem	Job Scheduling (IOI19_job)	C++17	100 / 100	160 ms	68544 KiB

job

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "jobscheduling"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;

/**
Cho 1 cây n đỉnh:
Cv i có parent là pi.
Cv i hoàn thành ở thời gian i có cost là t * u[i].
Cv i có thời gian hoàn thành là di.

Sắp xếp các cv sao cho các công việc pi luôn đứng trước i (trừ thằng 1).

subtask 1: cây đường thẳng.
Thì ta làm tuần tự.

subtask 2: Không có quan hệ ràng buộc cha con và d[i] = 1.
sort theo độ quan trọng của nó.

subtask 3: Không có quan hệ ràng buộc cha và con.
sort các đỉnh theo di / ui tăng dần.
Ta chứng minh được rằng nếu nó độc lập thì cách trên là tối ưu.

subtask 4: cây đường thẳng nhưng đỉnh 0 không nằm ở đầu đoạn thẳng.
Khi ta lấy 0 thì nó sẽ tách thành 2 đoạn thẳng.
**/

const int MAXN = 3e5 + 9;
int n;

namespace subtask1{
    bool check(){
        return n <= 10;
    }

    int solve(vector<int> p, vector<int> u, vector<int> d){
        int permutation[12], position[12];
        iota(permutation + 0, permutation + n, 0);
        int res = inf;
        do{
            int cur = 0;
            int ti =0;
            FOR(i, 0, n - 1){
                position[permutation[i]] = i;
                cur += (ti += d[permutation[i]]) * u[permutation[i]];
            }

            bool kt = true;
            FOR(i, 1, n - 1){
                if (position[p[i]] > position[i]) kt = false;
            }
            if (kt) minimize(res, cur);

        } while(next_permutation(permutation, permutation + n));
        return res;
    }
}
namespace subtask6{
    bool check(){
        return true;
    }
    struct pii{
        ll d, u, id;
        pii(int _d = 0, int _u = 0, int _id = 0): d(_d), u(_u), id(_id){}
        friend inline pii operator + (const pii &a, const pii &b){
            return pii(a.d + b.d, a.u + b.u, a.id);
        }

        friend inline pii operator - (const pii &a, const pii &b){
            return pii(a.d - b.d, a.u - b.u, a.id);
        }

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

        friend inline bool operator > (const pii &a, const pii &b){
            return (!(a < b));
        }

    };


    priority_queue<pii, vector<pii>, greater<pii>> pq[MAXN];
    vector<int> g[MAXN];
    pii a[MAXN];

    void dfs(int u){
        for(int v: g[u]){
            dfs(v); pq[u].push(a[v]);
        }

        while(!pq[u].empty()){
            if (pq[u].top() < a[u]){
                a[u] = a[u] + pq[u].top();

                int id = pq[u].top().id;
                pq[u].pop();

//                printf("MERGE: %lld %lld %lld\n", a[id].d, a[id].u, u, a[u].d, a[u].u);

                if (pq[u].size() < pq[id].size()) swap(pq[u], pq[id]);
                while(!pq[id].empty()){
                    pq[u].push(pq[id].top());
                    pq[id].pop();
                }
            }
            else break;
        }
    }

    long long get(vector<int> p, vector<int> u, vector<int> d){
        FOR(i, 1, n - 1){
            g[p[i]].pb(i);
        }

        FOR(i, 0, n - 1){
            a[i] = pii(d[i], u[i], i);
        }

        dfs(0);

        ll res = 0, cur = 0;
        priority_queue<pii, vector<pii>, greater<pii>> q;
        q.push(a[0]);
        while(!q.empty()){
            int id = q.top().id;
            q.pop();
            res += (cur += d[id]) * u[id];
//            printf("%lld\n", id);

            for(int v: g[id]){
                q.push(a[v]);
            }
        }
        return res;
    }

}
//d[i] / u[i];

long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d){
    n = u.size();
//    if (subtask1::check()) return subtask1::solve(p, u, d);
    if (subtask6::check()) return subtask6::get(p, u, d);
    return 0;
}

Compilation message (stderr)

job.cpp: In function 'int subtask1::solve(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:7:13: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    7 | #define inf 1e18
      |             ^~~~
job.cpp:56:19: note: in expansion of macro 'inf'
   56 |         int res = inf;
      |                   ^~~

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