#include "job.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pld pair<ld, ll>
#define fi first
#define se second
using namespace std;
const int N = 4e5+5;
const int M = 205;
const ll mod = 1e9+7;
const ld base = 1e-9;
ll n, m, k, ans, lab[N], cost[N], tim[N], id[N], par[N], t;
ld d[N];
struct node
{
bool operator ()(ll x, ll y) const
{
if(cost[x] * tim[y] == cost[y] * tim[x])return x < y;
cost[x] * tim[y] > cost[y] * tim[x];
}
};
ll findp(ll u)
{
return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
priority_queue<pld> pq;
ll scheduling_cost(vector<int> p, vector<int> c, vector<int> di)
{
n = p.size();
fill_n(lab, n+1, -1);
for(int i = 1; i <= n; i ++)
{
par[i] = p[i-1]+1;
cost[i] = c[i-1];
tim[i] = di[i-1];
d[i] = 1.0 * cost[i] / tim[i];
pq.push({d[i], i});
//cout << cost[i] <<" "<<tim[i]<<" ";
}
while(!pq.empty())
{
pld u = pq.top();
pq.pop();
if(abs(d[u.se]-u.fi) > base)continue;
//cout << (ld)u.fi <<" ";
if(!par[u.se] || d[findp(par[u.se])] == -1)
{
t += tim[u.se];
ans += t * cost[u.se];
d[u.se] = -1;
}
else
{
ll v = findp(par[u.se]);
ans -= cost[v] * tim[u.se];
cost[v] += cost[u.se];
tim[v] += tim[u.se];
lab[u.se] = v;
d[v] = 1.0 * cost[v] / tim[v];
pq.push({d[v], v});
}
}
return ans;
}
Compilation message
job.cpp: In member function 'bool node::operator()(long long int, long long int) const':
job.cpp:22:20: warning: statement has no effect [-Wunused-value]
22 | cost[x] * tim[y] > cost[y] * tim[x];
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
58 ms |
5548 KB |
Output is correct |
6 |
Correct |
137 ms |
12192 KB |
Output is correct |
7 |
Correct |
222 ms |
20912 KB |
Output is correct |
8 |
Correct |
303 ms |
23956 KB |
Output is correct |
9 |
Correct |
304 ms |
24076 KB |
Output is correct |
10 |
Correct |
294 ms |
24016 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
293 ms |
24072 KB |
Output is correct |
13 |
Correct |
247 ms |
23956 KB |
Output is correct |
14 |
Correct |
265 ms |
23980 KB |
Output is correct |
15 |
Correct |
205 ms |
24008 KB |
Output is correct |
16 |
Incorrect |
223 ms |
23980 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
178 ms |
20780 KB |
Output is correct |
5 |
Correct |
171 ms |
20780 KB |
Output is correct |
6 |
Correct |
173 ms |
20780 KB |
Output is correct |
7 |
Correct |
172 ms |
20772 KB |
Output is correct |
8 |
Correct |
176 ms |
20780 KB |
Output is correct |
9 |
Correct |
174 ms |
20900 KB |
Output is correct |
10 |
Correct |
169 ms |
20780 KB |
Output is correct |
11 |
Correct |
169 ms |
20776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
7 ms |
1608 KB |
Output is correct |
6 |
Correct |
176 ms |
20948 KB |
Output is correct |
7 |
Correct |
191 ms |
20780 KB |
Output is correct |
8 |
Correct |
166 ms |
20788 KB |
Output is correct |
9 |
Correct |
181 ms |
20896 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
6 ms |
1480 KB |
Output is correct |
13 |
Correct |
7 ms |
1608 KB |
Output is correct |
14 |
Correct |
187 ms |
20780 KB |
Output is correct |
15 |
Correct |
184 ms |
20780 KB |
Output is correct |
16 |
Correct |
173 ms |
20776 KB |
Output is correct |
17 |
Correct |
175 ms |
20832 KB |
Output is correct |
18 |
Correct |
173 ms |
20904 KB |
Output is correct |
19 |
Correct |
178 ms |
20884 KB |
Output is correct |
20 |
Correct |
173 ms |
20828 KB |
Output is correct |
21 |
Correct |
168 ms |
20776 KB |
Output is correct |
22 |
Correct |
175 ms |
20880 KB |
Output is correct |
23 |
Correct |
177 ms |
20896 KB |
Output is correct |
24 |
Correct |
180 ms |
20776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
319 ms |
20844 KB |
Output is correct |
3 |
Correct |
291 ms |
23956 KB |
Output is correct |
4 |
Correct |
299 ms |
24016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
58 ms |
5548 KB |
Output is correct |
6 |
Correct |
137 ms |
12192 KB |
Output is correct |
7 |
Correct |
222 ms |
20912 KB |
Output is correct |
8 |
Correct |
303 ms |
23956 KB |
Output is correct |
9 |
Correct |
304 ms |
24076 KB |
Output is correct |
10 |
Correct |
294 ms |
24016 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
293 ms |
24072 KB |
Output is correct |
13 |
Correct |
247 ms |
23956 KB |
Output is correct |
14 |
Correct |
265 ms |
23980 KB |
Output is correct |
15 |
Correct |
205 ms |
24008 KB |
Output is correct |
16 |
Incorrect |
223 ms |
23980 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |