| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 154861 | pink_bittern | Job Scheduling (IOI19_job) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <complex>
#define pb push_back
#define pll pair <ll, ll>
#define MOMI using namespace std;
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma optimize("TKACHENKO-GORYACHENKO")
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef long double ld;
using namespace std;
const ll maxn = 2e5 + 100;
ll n, m, k;
ll P[maxn];
ll U[maxn];
ll D[maxn];
ll ans = 0;
vector <ll> V[maxn];
pll ANS[maxn];
bool BAD[maxn];
bool cmp(pll a, pll b){
return a.first * b.second < b.first * a.second;
}
bool cmp1(ll a, ll b){
return cmp(ANS[a], ANS[b]);
}
void dfs(ll v, ll p){
ll q;
vector <ll> S;
for (q = 0; q < V[v].size(); q++){
if (V[v][q] == p){
continue;
}
S.pb(V[v][q]);
dfs(V[v][q], v);
}
pll cur = mp(D[v], U[v]);
sort(S.begin(), S.end(), cmp1);
ll j = S.size(), t = D[v];
for (q = 0; q < S.size(); q++){
ll v1 = S[q];
if (!cmp(ANS[v1], cur)){
j = q;
break;
}
else{
cur.first += ANS[v1].first;
cur.second += ANS[v1].second;
BAD[v1] = 1;
}
}
ans -= (cur.first - t) * (U[v]);
for (q = 0; q < j; q++){
ll v1 = S[q];
t += ANS[v1].first;
ans -= (cur.first - t) * (ANS[v1].second);
}
ANS[v] = cur;
// cout << v << " CUR " << cur.first << " " << cur.second << endl;
}
ll scheduling_cost(vector <int> p, vector <int> u, vector <int> d){
n = p.size();
bool is_bamboo = 1;
ll q, w, e, a, b;
for (q = 0; q < n; q++){
P[q] = p[q];
U[q] = u[q];
D[q] = d[q];
if (p[q] != q - 1){
is_bamboo = 0;
}
if (p[q] != -1){
V[p[q]].pb(q);
V[q].pb(p[q]);
}
}
if (is_bamboo){
ll t = 0;
for (q = 0; q < n; q++){
t += d[q];
ans += t * u[q];
}
return ans;
}
dfs(0, 0);
vector <ll> ALL;
for (q = 0; q < n; q++){
ALL.pb(q);
}
sort(ALL.begin(), ALL.end(), cmp1);
ll t = 0;
for (q = 0; q < ALL.size(); q++){
if (BAD[ALL[q]]){
continue;
}
t += ANS[ALL[q]].first;
ans += ANS[ALL[q]].second * t;
}
return ans;
}
int main(){
ll q, w, e, t, a, b, c;
cin >> n;
vector <int> p(n), u(n), d(n);
for (q = 0; q < n; q++){
cin >> p[q];
}
for (q = 0; q < n; q++){
cin >> u[q];
}
for (q = 0; q < n; q++){
cin >> d[q];
}
cout << scheduling_cost(p, u, d);
return 0;
}