Submission #313669

#	Time	Username	Problem	Language	Result	Execution time	Memory
313669		MiricaMatei	Job Scheduling (IOI19_job)	C++14	24 / 100	203 ms	31860 KiB

job

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200005;

vector<int>G[MAXN];
long long U[MAXN], D[MAXN];

void dfs(int node, int papa) {
  for (auto it:G[node])
    if (it != papa) {
      dfs(it, node);
      U[node] += U[it];
      D[node] += D[it];
    }
}

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();
  for (int i = 0; i < n; ++i)
    U[i] = u[i], D[i] = d[i];
  for (int i = 1; i < n; ++i)
    G[p[i]].push_back(i);
  dfs(0, -1);
  long long ans = 0;
  long long t = 0;
  priority_queue<Obj>pq;
  pq.push({0, U[0], D[0]});
  while (!pq.empty()) {
    Obj aux = pq.top();
    pq.pop();
    t += d[aux.i];
    ans += t * u[aux.i];
    for (auto it:G[aux.i])
      pq.push({it, U[it], D[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