oj.uz

Submission #473870

# Submission time Handle Problem Language Result Execution time Memory
473870 2021-09-16T10:56:39 Z Killer2501 Job Scheduling (IOI19_job) C++14
58 / 100
 330 ms 20912 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 ll mod = 1e9+7;
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] = 100000.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] = 100000.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];
      |   ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 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 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 56 ms 5556 KB Output is correct
6 Correct 125 ms 10620 KB Output is correct
7 Correct 214 ms 18480 KB Output is correct
8 Correct 295 ms 20792 KB Output is correct
9 Correct 330 ms 20776 KB Output is correct
10 Correct 294 ms 20792 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 307 ms 20832 KB Output is correct
13 Correct 250 ms 20888 KB Output is correct
14 Correct 249 ms 20828 KB Output is correct
15 Correct 201 ms 20828 KB Output is correct
16 Incorrect 224 ms 20776 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 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 189 ms 20836 KB Output is correct
5 Correct 174 ms 20912 KB Output is correct
6 Correct 173 ms 20908 KB Output is correct
7 Correct 185 ms 20772 KB Output is correct
8 Correct 186 ms 20780 KB Output is correct
9 Correct 178 ms 20896 KB Output is correct
10 Correct 190 ms 20776 KB Output is correct
11 Correct 180 ms 20828 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 400 KB Output is correct
5 Correct 8 ms 1528 KB Output is correct
6 Correct 178 ms 20808 KB Output is correct
7 Correct 180 ms 20832 KB Output is correct
8 Correct 186 ms 20896 KB Output is correct
9 Correct 177 ms 20828 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 174 ms 20776 KB Output is correct
15 Correct 175 ms 20784 KB Output is correct
16 Correct 173 ms 20776 KB Output is correct
17 Correct 173 ms 20780 KB Output is correct
18 Correct 173 ms 20836 KB Output is correct
19 Correct 172 ms 20768 KB Output is correct
20 Correct 170 ms 20792 KB Output is correct
21 Correct 182 ms 20896 KB Output is correct
22 Correct 183 ms 20744 KB Output is correct
23 Correct 176 ms 20800 KB Output is correct
24 Correct 173 ms 20788 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 308 ms 20840 KB Output is correct
3 Correct 289 ms 20796 KB Output is correct
4 Correct 308 ms 20896 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 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 332 KB Output is correct
7 Correct 0 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 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

Subtask #6
0 / 37.0

# 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 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 56 ms 5556 KB Output is correct
6 Correct 125 ms 10620 KB Output is correct
7 Correct 214 ms 18480 KB Output is correct
8 Correct 295 ms 20792 KB Output is correct
9 Correct 330 ms 20776 KB Output is correct
10 Correct 294 ms 20792 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 307 ms 20832 KB Output is correct
13 Correct 250 ms 20888 KB Output is correct
14 Correct 249 ms 20828 KB Output is correct
15 Correct 201 ms 20828 KB Output is correct
16 Incorrect 224 ms 20776 KB Output isn't correct
17 Halted 0 ms 0 KB -