oj.uz

Submission #473871

# Submission time Handle Problem Language Result Execution time Memory
473871 2021-09-16T10:57:44 Z Killer2501 Job Scheduling (IOI19_job) C++14
58 / 100
 370 ms 20908 KB 
#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 ld mod = 1e9;
const ld base = 1e-7;
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] = mod * 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] = mod * 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];
      |   ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 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 55 ms 5488 KB Output is correct
6 Correct 130 ms 10692 KB Output is correct
7 Correct 204 ms 18604 KB Output is correct
8 Correct 370 ms 20772 KB Output is correct
9 Correct 285 ms 20780 KB Output is correct
10 Correct 283 ms 20824 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 303 ms 20772 KB Output is correct
13 Correct 229 ms 20776 KB Output is correct
14 Correct 255 ms 20896 KB Output is correct
15 Correct 205 ms 20832 KB Output is correct
16 Incorrect 274 ms 20828 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 180 ms 20832 KB Output is correct
5 Correct 185 ms 20836 KB Output is correct
6 Correct 175 ms 20828 KB Output is correct
7 Correct 176 ms 20792 KB Output is correct
8 Correct 187 ms 20908 KB Output is correct
9 Correct 177 ms 20832 KB Output is correct
10 Correct 201 ms 20832 KB Output is correct
11 Correct 193 ms 20824 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 460 KB Output is correct
5 Correct 7 ms 1580 KB Output is correct
6 Correct 241 ms 20828 KB Output is correct
7 Correct 166 ms 20780 KB Output is correct
8 Correct 175 ms 20836 KB Output is correct
9 Correct 176 ms 20836 KB Output is correct
10 Correct 1 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 175 ms 20772 KB Output is correct
15 Correct 183 ms 20840 KB Output is correct
16 Correct 194 ms 20776 KB Output is correct
17 Correct 200 ms 20832 KB Output is correct
18 Correct 193 ms 20832 KB Output is correct
19 Correct 171 ms 20828 KB Output is correct
20 Correct 211 ms 20836 KB Output is correct
21 Correct 170 ms 20832 KB Output is correct
22 Correct 185 ms 20824 KB Output is correct
23 Correct 174 ms 20784 KB Output is correct
24 Correct 170 ms 20776 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 319 ms 20836 KB Output is correct
3 Correct 302 ms 20776 KB Output is correct
4 Correct 313 ms 20908 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 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 344 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

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 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 55 ms 5488 KB Output is correct
6 Correct 130 ms 10692 KB Output is correct
7 Correct 204 ms 18604 KB Output is correct
8 Correct 370 ms 20772 KB Output is correct
9 Correct 285 ms 20780 KB Output is correct
10 Correct 283 ms 20824 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 303 ms 20772 KB Output is correct
13 Correct 229 ms 20776 KB Output is correct
14 Correct 255 ms 20896 KB Output is correct
15 Correct 205 ms 20832 KB Output is correct
16 Incorrect 274 ms 20828 KB Output isn't correct
17 Halted 0 ms 0 KB -