oj.uz

Submission #201396

# Submission time Handle Problem Language Result Execution time Memory
201396 2020-02-10T11:17:50 Z spdskatr Job Scheduling (IOI19_job) C++14
19 / 100
 1084 ms 262148 KB 
#include "job.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <utility>
#include <cstring>
#include <vector>
#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 {
		int av = a.fi.fi * b.fi.se;
		int 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);
		int par = p[e.se];
		// Merge with parent
		ll nu = uu[f(par)] + uu[f(e.se)];
		ll nd = dd[f(par)] + dd[f(e.se)];
		s.erase({ { uu[f(par)], dd[f(par)] }, f(par) });
		v[f(par)].push_back(f(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

job.cpp: In function 'void dfs(int)':
job.cpp:38: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:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ord.size(); i++) {
                  ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 8 ms 4984 KB Output is correct
4 Runtime error 509 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 8 ms 4988 KB Output is correct
3 Correct 8 ms 4984 KB Output is correct
4 Correct 331 ms 29172 KB Output is correct
5 Correct 295 ms 29108 KB Output is correct
6 Correct 338 ms 29120 KB Output is correct
7 Correct 306 ms 29044 KB Output is correct
8 Correct 320 ms 29300 KB Output is correct
9 Correct 303 ms 29044 KB Output is correct
10 Correct 317 ms 29044 KB Output is correct
11 Correct 329 ms 29044 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 8 ms 5016 KB Output is correct
3 Correct 8 ms 4984 KB Output is correct
4 Correct 9 ms 5056 KB Output is correct
5 Correct 16 ms 6264 KB Output is correct
6 Correct 349 ms 29684 KB Output is correct
7 Correct 346 ms 29668 KB Output is correct
8 Correct 327 ms 29680 KB Output is correct
9 Correct 332 ms 29668 KB Output is correct
10 Correct 8 ms 4984 KB Output is correct
11 Correct 9 ms 5240 KB Output is correct
12 Correct 20 ms 6136 KB Output is correct
13 Correct 16 ms 6272 KB Output is correct
14 Correct 325 ms 29660 KB Output is correct
15 Correct 343 ms 29660 KB Output is correct
16 Correct 328 ms 29712 KB Output is correct
17 Correct 341 ms 29680 KB Output is correct
18 Correct 330 ms 29600 KB Output is correct
19 Correct 330 ms 29684 KB Output is correct
20 Correct 324 ms 29560 KB Output is correct
21 Correct 334 ms 29556 KB Output is correct
22 Correct 316 ms 29684 KB Output is correct
23 Correct 318 ms 29684 KB Output is correct
24 Correct 313 ms 29556 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Runtime error 1084 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Correct 9 ms 4984 KB Output is correct
4 Correct 8 ms 4984 KB Output is correct
5 Correct 8 ms 4984 KB Output is correct
6 Correct 7 ms 4984 KB Output is correct
7 Correct 8 ms 4984 KB Output is correct
8 Correct 8 ms 4984 KB Output is correct
9 Correct 8 ms 4984 KB Output is correct
10 Runtime error 266 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 8 ms 4984 KB Output is correct
4 Runtime error 509 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -