# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
155072 | neki | Job Scheduling (IOI19_job) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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{
ll 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<ll> P, vector<ll> U, vector<ll> 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]].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;
t[P[nek.id]].d+=t[nek.id].d;
ans+=t[P[nek.id]].d * t[nek.id].u;
t[P[nek.id]].u+=t[nek.id].u;
for(auto&& j : t[nek.id].chs) P[j]=P[nek.id];
if(nek.id!=n&&act[P[nek.id]) q.push(ts[P[nek.id]]);
}
}
return ans;
}