oj.uz

Submission #1010398

# Submission time Handle Problem Language Result Execution time Memory
1010398 2024-06-29T04:24:56 Z vjudge1 Job Scheduling (IOI19_job) C++17
7 / 100
 110 ms 16816 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair <int, int> ii;

const int N = 2e5 + 5;
long long n, dp[N], cost[N], d[N], lab[N], res;

struct obj {
	int sum_d, sum_cost;
	bool operator < (const obj other) const {
		return sum_d * other.sum_cost > other.sum_d * sum_cost;
	}
	bool operator != (const obj other) const {
		return ii(sum_d, sum_cost) != ii(other.sum_d, other.sum_cost);
	}
} a[N];

int root(int x) {
	if (lab[x] == -1) return x;
	else return lab[x] = root(lab[x]);
}

long long scheduling_cost(vector <int32_t> p, vector <int32_t> c, vector <int32_t> time) {
	memset(lab, -1, sizeof lab);	
	n = p.size();
	priority_queue <pair <obj, int>> pq;
	while (!pq.empty()) pq.pop();
	for (int i = 0; i < n; ++i) {
		cost[i] = c[i];
		d[i] = time[i];
		a[i] = {d[i], cost[i]};
		res += d[i] * cost[i];
		pq.push({a[i], i});
	}
	while (!pq.empty()) {
		obj cur = pq.top().first; int u = pq.top().second;
		pq.pop();
		if (cur != a[u] || u == 0) continue;
		int v = root(p[u]);
		res += a[v].sum_d * a[u].sum_cost;
		a[v].sum_d += a[u].sum_d; a[v].sum_cost += a[u].sum_cost;
		lab[u] = v;
		pq.push({a[v], v});
	}
	return res;
}

Compilation message

job.cpp: In function 'long long int scheduling_cost(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:32:14: warning: narrowing conversion of 'd[i]' from 'long long int' to 'int' [-Wnarrowing]
   32 |   a[i] = {d[i], cost[i]};
      |           ~~~^
job.cpp:32:23: warning: narrowing conversion of 'cost[i]' from 'long long int' to 'int' [-Wnarrowing]
   32 |   a[i] = {d[i], cost[i]};
      |                 ~~~~~~^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Incorrect 1 ms 1884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 105 ms 15556 KB Output is correct
5 Correct 104 ms 15564 KB Output is correct
6 Correct 97 ms 15560 KB Output is correct
7 Correct 89 ms 15608 KB Output is correct
8 Correct 92 ms 15500 KB Output is correct
9 Correct 96 ms 15560 KB Output is correct
10 Correct 98 ms 15560 KB Output is correct
11 Correct 91 ms 15556 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Incorrect 1 ms 1884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Incorrect 110 ms 16816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Incorrect 1 ms 1884 KB Output isn't correct
4 Halted 0 ms 0 KB -