답안 #587358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587358	2022-07-01T17:20:41 Z	blue	Job Scheduling (IOI19_job)	C++17	100 / 100	676 ms	23984 KB

#include "job.h"
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define sz(x) int(x.size())

ll res = 0;

const int mx = 200'000;

struct dsu
{
	vi par = vi(1+mx);
	vi st = vi(1+mx, 1);
	vi peak = vi(1+mx);

	dsu()
	{
		for(int i = 0; i <= mx; i++)
		{
			par[i] = i;
			peak[i] = i;
		}
	}

	int root(int u)
	{
		if(par[u] == u) return u;
		else return (par[u] = root(par[u]));
	}

	int getpeak(int u)
	{
		return peak[root(u)];
	}

	bool join(int u, int v, int p)
	{
		u = root(u);
		v = root(v);

		if(u == v)
			return 0;

		if(st[u] < st[v])
			swap(u, v);

		par[v] = u;
		st[u] += st[v];
		peak[u] = p;

		return 1;
	}
};	

int n;

vi p;
vll u, d;

struct temple
{
	int i;
};

bool operator < (temple A, temple B)
{
	if(d[A.i]*u[B.i] == d[B.i]*u[A.i])
		return A.i < B.i;
	else
		return d[A.i]*u[B.i] < d[B.i]*u[A.i];
}

ll scheduling_cost(vi p_, vi u_, vi d_) 
{
	p = p_;
	n = sz(p);

	u = d = vll(n);
	for(int i = 0; i < n; i++)
	{
		u[i] = u_[i];
		d[i] = d_[i];
	}

	dsu ds;

	for(int i = 0; i < n; i++)
		res += u[i]*d[i];

	set<temple> S;
	for(int i = 1; i < n; i++)
		S.insert(temple{i});	

	//combined values are stored at the paek

	for(int t = 0; t < n-1; t++)
	{
		int a = S.begin()->i;
		S.erase(S.begin());

		int pa = ds.getpeak(a);

		int b = p[pa];
		int pb = ds.getpeak(b);

		res += d[pb] * u[pa];

		
		ds.join(pa, pb, pb);

		if(pb == 0)
		{
			d[pb] += d[pa];
			u[pb] += u[pa];
		}
		else
		{
			S.erase(temple{pb});

			d[pb] += d[pa];
			u[pb] += u[pa];

			S.insert(temple{pb});
		}
	}


	return res;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	3 ms	2644 KB	Output is correct
5	Correct	83 ms	7820 KB	Output is correct
6	Correct	243 ms	13180 KB	Output is correct
7	Correct	423 ms	18500 KB	Output is correct
8	Correct	609 ms	23836 KB	Output is correct
9	Correct	572 ms	23836 KB	Output is correct
10	Correct	612 ms	23832 KB	Output is correct
11	Correct	2 ms	2644 KB	Output is correct
12	Correct	620 ms	23832 KB	Output is correct
13	Correct	372 ms	23716 KB	Output is correct
14	Correct	333 ms	23836 KB	Output is correct
15	Correct	198 ms	23808 KB	Output is correct
16	Correct	237 ms	23836 KB	Output is correct
17	Correct	573 ms	23832 KB	Output is correct
18	Correct	626 ms	23840 KB	Output is correct
19	Correct	193 ms	23836 KB	Output is correct
20	Correct	193 ms	23840 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	341 ms	22404 KB	Output is correct
5	Correct	260 ms	22380 KB	Output is correct
6	Correct	243 ms	22400 KB	Output is correct
7	Correct	283 ms	22476 KB	Output is correct
8	Correct	260 ms	22516 KB	Output is correct
9	Correct	280 ms	22296 KB	Output is correct
10	Correct	223 ms	22308 KB	Output is correct
11	Correct	232 ms	22332 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	2 ms	2516 KB	Output is correct
3	Correct	2 ms	2588 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	8 ms	3628 KB	Output is correct
6	Correct	242 ms	22892 KB	Output is correct
7	Correct	238 ms	22856 KB	Output is correct
8	Correct	237 ms	22968 KB	Output is correct
9	Correct	221 ms	23004 KB	Output is correct
10	Correct	2 ms	2644 KB	Output is correct
11	Correct	3 ms	2772 KB	Output is correct
12	Correct	7 ms	3496 KB	Output is correct
13	Correct	7 ms	3540 KB	Output is correct
14	Correct	259 ms	22956 KB	Output is correct
15	Correct	213 ms	22856 KB	Output is correct
16	Correct	238 ms	22872 KB	Output is correct
17	Correct	242 ms	22968 KB	Output is correct
18	Correct	212 ms	22860 KB	Output is correct
19	Correct	242 ms	22888 KB	Output is correct
20	Correct	242 ms	22948 KB	Output is correct
21	Correct	222 ms	22968 KB	Output is correct
22	Correct	259 ms	22956 KB	Output is correct
23	Correct	222 ms	22844 KB	Output is correct
24	Correct	255 ms	22892 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	597 ms	23896 KB	Output is correct
3	Correct	624 ms	23888 KB	Output is correct
4	Correct	676 ms	23836 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2596 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	2 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2644 KB	Output is correct
9	Correct	2 ms	2644 KB	Output is correct
10	Correct	2 ms	2644 KB	Output is correct
11	Correct	2 ms	2644 KB	Output is correct
12	Correct	2 ms	2592 KB	Output is correct
13	Correct	1 ms	2644 KB	Output is correct
14	Correct	2 ms	2644 KB	Output is correct
15	Correct	1 ms	2644 KB	Output is correct
16	Correct	2 ms	2644 KB	Output is correct
17	Correct	2 ms	2644 KB	Output is correct

Subtask #6
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	3 ms	2644 KB	Output is correct
5	Correct	83 ms	7820 KB	Output is correct
6	Correct	243 ms	13180 KB	Output is correct
7	Correct	423 ms	18500 KB	Output is correct
8	Correct	609 ms	23836 KB	Output is correct
9	Correct	572 ms	23836 KB	Output is correct
10	Correct	612 ms	23832 KB	Output is correct
11	Correct	2 ms	2644 KB	Output is correct
12	Correct	620 ms	23832 KB	Output is correct
13	Correct	372 ms	23716 KB	Output is correct
14	Correct	333 ms	23836 KB	Output is correct
15	Correct	198 ms	23808 KB	Output is correct
16	Correct	237 ms	23836 KB	Output is correct
17	Correct	573 ms	23832 KB	Output is correct
18	Correct	626 ms	23840 KB	Output is correct
19	Correct	193 ms	23836 KB	Output is correct
20	Correct	193 ms	23840 KB	Output is correct
21	Correct	3 ms	2644 KB	Output is correct
22	Correct	2 ms	2644 KB	Output is correct
23	Correct	2 ms	2644 KB	Output is correct
24	Correct	341 ms	22404 KB	Output is correct
25	Correct	260 ms	22380 KB	Output is correct
26	Correct	243 ms	22400 KB	Output is correct
27	Correct	283 ms	22476 KB	Output is correct
28	Correct	260 ms	22516 KB	Output is correct
29	Correct	280 ms	22296 KB	Output is correct
30	Correct	223 ms	22308 KB	Output is correct
31	Correct	232 ms	22332 KB	Output is correct
32	Correct	1 ms	2644 KB	Output is correct
33	Correct	2 ms	2516 KB	Output is correct
34	Correct	2 ms	2588 KB	Output is correct
35	Correct	2 ms	2644 KB	Output is correct
36	Correct	8 ms	3628 KB	Output is correct
37	Correct	242 ms	22892 KB	Output is correct
38	Correct	238 ms	22856 KB	Output is correct
39	Correct	237 ms	22968 KB	Output is correct
40	Correct	221 ms	23004 KB	Output is correct
41	Correct	2 ms	2644 KB	Output is correct
42	Correct	3 ms	2772 KB	Output is correct
43	Correct	7 ms	3496 KB	Output is correct
44	Correct	7 ms	3540 KB	Output is correct
45	Correct	259 ms	22956 KB	Output is correct
46	Correct	213 ms	22856 KB	Output is correct
47	Correct	238 ms	22872 KB	Output is correct
48	Correct	242 ms	22968 KB	Output is correct
49	Correct	212 ms	22860 KB	Output is correct
50	Correct	242 ms	22888 KB	Output is correct
51	Correct	242 ms	22948 KB	Output is correct
52	Correct	222 ms	22968 KB	Output is correct
53	Correct	259 ms	22956 KB	Output is correct
54	Correct	222 ms	22844 KB	Output is correct
55	Correct	255 ms	22892 KB	Output is correct
56	Correct	2 ms	2644 KB	Output is correct
57	Correct	597 ms	23896 KB	Output is correct
58	Correct	624 ms	23888 KB	Output is correct
59	Correct	676 ms	23836 KB	Output is correct
60	Correct	2 ms	2644 KB	Output is correct
61	Correct	2 ms	2644 KB	Output is correct
62	Correct	2 ms	2596 KB	Output is correct
63	Correct	2 ms	2644 KB	Output is correct
64	Correct	2 ms	2644 KB	Output is correct
65	Correct	2 ms	2644 KB	Output is correct
66	Correct	2 ms	2644 KB	Output is correct
67	Correct	2 ms	2644 KB	Output is correct
68	Correct	2 ms	2644 KB	Output is correct
69	Correct	2 ms	2644 KB	Output is correct
70	Correct	2 ms	2644 KB	Output is correct
71	Correct	2 ms	2592 KB	Output is correct
72	Correct	1 ms	2644 KB	Output is correct
73	Correct	2 ms	2644 KB	Output is correct
74	Correct	1 ms	2644 KB	Output is correct
75	Correct	2 ms	2644 KB	Output is correct
76	Correct	2 ms	2644 KB	Output is correct
77	Correct	2 ms	2644 KB	Output is correct
78	Correct	2 ms	2644 KB	Output is correct
79	Correct	2 ms	2644 KB	Output is correct
80	Correct	2 ms	2644 KB	Output is correct
81	Correct	2 ms	2644 KB	Output is correct
82	Correct	2 ms	2644 KB	Output is correct
83	Correct	2 ms	2644 KB	Output is correct
84	Correct	2 ms	2644 KB	Output is correct
85	Correct	2 ms	2588 KB	Output is correct
86	Correct	2 ms	2644 KB	Output is correct
87	Correct	2 ms	2644 KB	Output is correct
88	Correct	6 ms	3156 KB	Output is correct
89	Correct	9 ms	3372 KB	Output is correct
90	Correct	11 ms	3668 KB	Output is correct
91	Correct	60 ms	7872 KB	Output is correct
92	Correct	158 ms	13036 KB	Output is correct
93	Correct	476 ms	23732 KB	Output is correct
94	Correct	497 ms	23764 KB	Output is correct
95	Correct	438 ms	23736 KB	Output is correct
96	Correct	499 ms	23736 KB	Output is correct
97	Correct	417 ms	23744 KB	Output is correct
98	Correct	394 ms	23824 KB	Output is correct
99	Correct	343 ms	23612 KB	Output is correct
100	Correct	482 ms	23756 KB	Output is correct
101	Correct	489 ms	23984 KB	Output is correct
102	Correct	238 ms	23732 KB	Output is correct
103	Correct	536 ms	23852 KB	Output is correct
104	Correct	520 ms	23904 KB	Output is correct
105	Correct	226 ms	23836 KB	Output is correct
106	Correct	217 ms	23072 KB	Output is correct

답안 #587358

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 12.0 / 12.0

Subtask #4 18.0 / 18.0

Subtask #5 21.0 / 21.0

Subtask #6 37.0 / 37.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
12.0 / 12.0

Subtask #4
18.0 / 18.0

Subtask #5
21.0 / 21.0

Subtask #6
37.0 / 37.0