Submission #251009

#	Time	Username	Problem	Language	Result	Execution time	Memory
251009		cjoa	Job Scheduling (IOI19_job)	C++14	24 / 100	113 ms	36472 KiB

job

#include "job.h"

#include <vector>
#include <algorithm>
//#include <iostream>

using namespace std;

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

int N;
VVI tree;
VI D, U;
vector<llong> sumD, sumU;
void dfs(int x) {
   sumD[x] = D[x];
   sumU[x] = U[x];
   for (int y : tree[x]) {
      dfs(y);
      sumD[x] += sumD[y];
      sumU[x] += sumU[y];
   }
}

llong dfs2(int x, llong T) {
   T += D[x];
   llong res = U[x] * T;

   sort(tree[x].begin(), tree[x].end(),
        [&] (int i, int j) -> bool {
            return sumD[i] * sumU[j] < sumD[j] * sumU[i];
        });

   for (int y : tree[x]) {
      res += dfs2(y, T);
      T += sumD[y];
   }
   return res;
}

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

   ::D = d;
   ::U = u;

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

   sumD.assign(N, 0);
   sumU.assign(N, 0);

   dfs(0);

// for (int x = 0; x < N; ++x)
//    cerr << x << ": " << sumD[x] << ' ' << sumU[x] << endl;

   llong res = dfs2(0, 0);

   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