Submission #155077

#	Time	Username	Problem	Language	Result	Execution time	Memory
155077		neki	Job Scheduling (IOI19_job)	C++14	0 / 100	10 ms	9720 KiB

job

#include "job.h"
#include <bits/stdc++.h>
using namespace std;
#define loop(i, a, b) for(int i=a;i<b;i++)
typedef long long ll;

struct t{
  vector<ll> chs;ll u, d, id;
  bool operator<(const t& oth) const {return u * oth.d>oth.u * d;}
};

t ts[200100];
int act[200100];
 
ll scheduling_cost(vector<int> P, vector<int> U, vector<int> D) {
  ll n=P.size(), ans=0;
  P.push_back(0), U.push_back(0), D.push_back(0);P[0]=n;
  loop(i, 1, n) ts[P[i]].chs.push_back(i);
  loop(i, 0, n) ts[i].u=U[i], ts[i].d=D[i], ts[i].id=i, act[i]=1;
  priority_queue<t> q;
  loop(i, 0, n) q.push(ts[i]);
  while(q.size()){
    t nek=q.top(); q.pop();
    if(act[nek.id]&&nek.u==ts[nek.id].u&&nek.d==ts[nek.id].d){
      act[nek.id]=0;
      ts[P[nek.id]].d+=ts[nek.id].d;
      ans+=ts[P[nek.id]].d * ts[nek.id].u;
      ts[P[nek.id]].u+=ts[nek.id].u;
      for(auto&& j : ts[nek.id].chs) P[j]=P[nek.id];
      if(nek.id!=n&&act[P[nek.id]]) q.push(ts[P[nek.id]]);
    }
  }
  return ans;
}

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