Submission #251359

#	Time	Username	Problem	Language	Result	Execution time	Memory
251359		cjoa	Job Scheduling (IOI19_job)	C++14	24 / 100	189 ms	19812 KiB

job

#include "job.h"

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long llong;

struct Temple {
   int id;
   llong days, cost;
   bool operator<(const Temple& t) const {
      return days * t.cost > t.days * cost;
   }
};

long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
   int N = p.size();
   VVI tree(N);

   for (int i = 1; i < N; ++i)
      tree[ p[i] ].push_back(i);

   llong T = 0;
   llong res = 0;

   priority_queue<Temple> pq;
   pq.push({0, d[0], u[0]});
   while (!pq.empty()) {
      Temple t = pq.top();
      pq.pop();
      T += d[t.id];
      res += T * u[t.id];
      for (int y : tree[t.id]) {
         pq.push({y, d[y], u[y]});
      }
   }

   return res;
}

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