Submission #201517

#	Time	Username	Problem	Language	Result	Execution time	Memory
201517		spdskatr	Job Scheduling (IOI19_job)	C++14	100 / 100	678 ms	35832 KiB

job

#include "job.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <utility>
#include <cstring>
#include <vector>
#include <cassert>
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<pll, int> entry;
struct comp {
	bool operator()(entry a, entry b) const {
		ll av = a.fi.fi * b.fi.se;
		ll bv = a.fi.se * b.fi.fi;
		if (av != bv) {
			return av < bv;
		}
		return a.se < b.se;
	}
};
set<entry, comp> s;
vector<int> v[200005];
vector<int> ord;
int N, uf[200005];

ll uu[200005], dd[200005];

int f(int x) { if (uf[x] == x) return x; return uf[x] = f(uf[x]); }
void un(int x, int y) { uf[f(x)] = f(y); }

void dfs(int x) {
	ord.push_back(x);
	for (int i = 0; i < v[x].size(); i++) {
		dfs(v[x][i]);
	}
}

ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
	int N = p.size();
	for (int i = 0; i < N; i++) uf[i] = i;
	for (int i = 1; i < N; i++) {
		uu[i] = u[i];
		dd[i] = d[i];
		v[i].clear();
	}
	for (int i = 1; i < N; i++) s.insert({ { u[i], d[i] }, i });
	while (s.size() > 0) {
		auto it = --s.end();
		entry e = *it;
		s.erase(it);
		//assert(f(e.se) == e.se);
		int par = p[e.se];
		// Merge with parent
		ll nu = uu[f(par)] + uu[e.se];
		ll nd = dd[f(par)] + dd[e.se];
		int en = s.erase((entry){ { uu[f(par)], dd[f(par)] }, f(par) });
		v[f(par)].push_back(e.se);
		un(e.se, par);
		uu[f(par)] = nu;
		dd[f(par)] = nd;
		if (f(par) != 0) s.insert({ { uu[f(par)], dd[f(par)] }, f(par) });
	}
	dfs(0);
	ll tm = 0, ans = 0;
	for (int i = 0; i < ord.size(); i++) {
		tm += d[ord[i]];
		ans += tm * u[ord[i]];
	}
	return ans;
}

Compilation message (stderr)

job.cpp: In function 'void dfs(int)':
job.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[x].size(); i++) {
                  ~~^~~~~~~~~~~~~
job.cpp: In function 'll scheduling_cost(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:62:7: warning: unused variable 'en' [-Wunused-variable]
   int en = s.erase((entry){ { uu[f(par)], dd[f(par)] }, f(par) });
       ^~
job.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ord.size(); i++) {
                  ~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 37 / 37