Submission #1010398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010398		vjudge1	Job Scheduling (IOI19_job)	C++17	7 / 100	110 ms	16816 KiB

job

#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 (stderr)

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
• Subtask 2: 7 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 37