Submission #313676

#	Time	Username	Problem	Language	Result	Execution time	Memory
313676		MiricaMatei	Job Scheduling (IOI19_job)	C++14	24 / 100	174 ms	12644 KiB

job

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200005;

bool vis[MAXN];

struct Obj {
  long long i, u, d;
  bool operator <(const Obj& other) const {
    bool ans;
    if (u == 0) {
      ans = 0;
    } else {
      if (other.u == 0) {
        ans = 1;
      } else {
        if (1LL * d * other.u < 1LL * other.d * u)
          ans = 1;
        else
          ans = 0;
      }
    }
    return !ans;
  }
};

long long scheduling_cost(vector<int>p, vector<int>u, vector<int>d) {
  int n = p.size();
  priority_queue<Obj>pq;
  for (int i = 1; i < n; ++i)
    pq.push({i, u[i], d[i]});
  vector<int>v;
  v.push_back(0);
  vis[0] = 1;
  while (!pq.empty()) {
    Obj aux = pq.top();
    pq.pop();
    vector<int>a;
    int x = aux.i;
    while (!vis[x]) {
      a.push_back(x);
      vis[x] = 1;
      x = p[x];
    }
    reverse(a.begin(), a.end());
    for (auto it:a)
      v.push_back(it);
  }
  long long ans = 0;
  long long t = 0;
  for (auto it:v) {
    t += d[it];
    ans += t * u[it];
  }
  return ans;
}

/*int main() {
  freopen("date.in", "r", stdin);
  freopen("date.out", "w", stdout);

  int n;
  scanf("%d", &n);
  vector<int>p(n), u(n), d(n);
  for (int i = 0; i < n; ++i)
    scanf("%d", &p[i]);
  for (int i = 0; i < n; ++i)
    scanf("%d", &u[i]);
  for (int i = 0; i < n; ++i)
    scanf("%d", &d[i]);

  printf("%lld\n", scheduling_cost(p, u, d));

  return 0;
}*/

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