oj.uz

Submission #464771

# Submission time Handle Problem Language Result Execution time Memory
464771 2021-08-14T02:47:31 Z HappyPacMan Job Scheduling (IOI19_job) C++14
0 / 100
 90 ms 13880 KB 
#include "job.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 13;
int dsu[N];

int ufds(int u){
	return dsu[u] = u == dsu[u] ? u : ufds(dsu[u]);
}

struct Comp{
	const bool operator() (tuple<int,int,int> a,tuple<int,int,int> b){
		return get<0>(a)*get<1>(b) < get<1>(a)*get<0>(b);
	}
};

long long scheduling_cost(vector<int> p,vector<int> u,vector<int> d){
	int n = p.size();
	iota(dsu,dsu+n,0);
	long long cost = 0;
	for(int i=0;i<n;i++) cost += u[i] * 1LL * d[i];
	priority_queue<tuple<int,int,int>,vector<tuple<int,int,int> >,Comp> pq;
	for(int i=0;i<n;i++) pq.emplace(u[i],d[i],i);
	while(!pq.empty()){
		auto curr = pq.top();
		int ux = get<0>(curr);
		int id = get<2>(curr);
		pq.pop();
		if(ux != u[id]) continue;
		if(id){
			int pr = ufds(p[id]);
			cost += u[id] * 1LL * d[pr];
			dsu[id] = pr;
			u[pr] += u[id];
			d[pr] += d[id];
			pq.emplace(u[pr],d[pr],pr);
		}
	}
	return cost;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 40 ms 3316 KB Output is correct
6 Correct 90 ms 6184 KB Output is correct
7 Runtime error 52 ms 10604 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Runtime error 63 ms 10744 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Runtime error 74 ms 13880 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 40 ms 3316 KB Output is correct
6 Correct 90 ms 6184 KB Output is correct
7 Runtime error 52 ms 10604 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -