#include "job.h"
#include <bits/extc++.h>
#include <vector>
#define pb emplace_back
const int maxn = 200010;
using ll = long long;
using namespace std;
int deg[maxn], togo[maxn], tl, n;
ll res;
vector<int> edge[maxn], sorted[maxn];
ll p[maxn], u[maxn], d[maxn];
struct cmp {
bool operator()(int a, int b) const {
return d[a] * u[b] > d[b] * u[a];
}
};
void sub_merge(int a, int b) {
res -= (ll)d[b] * u[a];
d[a] += d[b];
u[a] += u[b];
}
void get_ans() {
for (int i = 0;i < n;++i) {
int now = togo[i];
assert(now || i == n-1);
for (int u : edge[now]) {
if (sorted[u].size() > sorted[now].size()) swap(sorted[u], sorted[now]);
int a = sorted[now].size();
sorted[now].insert(sorted[now].end(), sorted[u].begin(), sorted[u].end());
inplace_merge(sorted[now].begin(), sorted[now].begin()+a, sorted[now].end(), cmp());
}
while (sorted[now].size() && cmp()(now, sorted[now].back())) {
sub_merge(now, sorted[now].back());
sorted[now].pop_back();
}
sorted[now].pb(now);
}
auto &v = sorted[0];
ll t = 0;
auto dojob = [&](int a) {
cerr << "dojob " << a << ' ' << "d, u : " << d[a] << ' ' << u[a] << '\n';
t += d[a];
res += t * u[a];
};
while (v.size()) {
dojob(v.back());
v.pop_back();
}
}
long long bf() {
static bool did[maxn];
auto &v = edge[0];
sort(v.begin(), v.end(), cmp());
for (int u : v)assert(u);
ll t = 0;
ll res = 0;
auto dojob = [&](int a) {
t += d[a];
res += t * u[a];
};
dojob(0);
for (int i = (int)v.size()-1;i >= 0;--i)
dojob(v[i]);
return res;
}
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
n = p.size();
for (int i = 1;i < n;++i) edge[p[i]].pb(i);
for (int i = 1;i < n;++i) ++deg[ p[i] ];
for (int i = 0;i < n;++i) if (deg[i] == 0)
togo[tl++] = i;
for (int i = 0;i < n;++i) {
int now = togo[i];
if (now == 0) {
assert(n-1 == i);
break;
}
if ( --deg[ p[now] ] == 0) togo[tl++] = p[now];
}
for (int i = 0;i < n;++i)
::p[i] = p[i], ::u[i] = u[i], ::d[i] = d[i];
get_ans();
return res;
//cerr << "my ans is : " << res << '\n';
//res = 0;
//cerr << "brute force : " << bf() << '\n';
return bf();
}
Compilation message
job.cpp: In function 'long long int bf()':
job.cpp:51:14: warning: unused variable 'did' [-Wunused-variable]
static bool did[maxn];
^~~
job.cpp: At global scope:
job.cpp:51:14: warning: 'did' defined but not used [-Wunused-variable]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9728 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
9856 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
