oj.uz

Submission #473858

# Submission time Handle Problem Language Result Execution time Memory
473858 2021-09-16T10:51:24 Z Killer2501 Job Scheduling (IOI19_job) C++14
40 / 100
 302 ms 23964 KB 
#include <bits/stdc++.h>
#define ll long long
#include "job.h"
#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-6;
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];
      |   ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.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 Incorrect 65 ms 6292 KB Output isn't correct
6 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 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 174 ms 22604 KB Output is correct
5 Correct 174 ms 22556 KB Output is correct
6 Correct 175 ms 22564 KB Output is correct
7 Correct 181 ms 22556 KB Output is correct
8 Correct 191 ms 22688 KB Output is correct
9 Correct 178 ms 22556 KB Output is correct
10 Correct 189 ms 22560 KB Output is correct
11 Correct 191 ms 22676 KB Output is correct

Subtask #3
12.0 / 12.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 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 7 ms 1680 KB Output is correct
6 Correct 182 ms 23136 KB Output is correct
7 Correct 187 ms 23200 KB Output is correct
8 Correct 175 ms 23064 KB Output is correct
9 Correct 186 ms 23188 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 1608 KB Output is correct
13 Correct 7 ms 1608 KB Output is correct
14 Correct 173 ms 23084 KB Output is correct
15 Correct 172 ms 23064 KB Output is correct
16 Correct 183 ms 23060 KB Output is correct
17 Correct 178 ms 23084 KB Output is correct
18 Correct 170 ms 23084 KB Output is correct
19 Correct 175 ms 23192 KB Output is correct
20 Correct 182 ms 23144 KB Output is correct
21 Correct 183 ms 23180 KB Output is correct
22 Correct 171 ms 23060 KB Output is correct
23 Correct 184 ms 23084 KB Output is correct
24 Correct 177 ms 23156 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 302 ms 23964 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 1 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

Subtask #6
0 / 37.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 Incorrect 65 ms 6292 KB Output isn't correct
6 Halted 0 ms 0 KB -