답안 #26603 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26603	2017-07-03T12:41:57 Z	kriii	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	62 ms	7684 KB

#include "Joi.h"
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	vector<vector<int> > graph;
	vector<vector<int> > groups;
	vector<bool> chk(N);
	vector<int> grp;

	graph.resize(N);
	for (int i=0;i<M;i++){
		graph[A[i]].push_back(B[i]);
		graph[B[i]].push_back(A[i]);
	}
	for (int i=0;i<N;i++) sort(graph[i].begin(),graph[i].end());

	function<void(int, int)> dfs;
	dfs = [&](int x, int lim){
		grp.push_back(x);
		chk[x] = 1;
		if (grp.size() == lim) return;
		for (auto &y : graph[x]) if (!chk[y]){
			dfs(y,lim);
			if (grp.size() == lim) return;
		}
	};

	vector<int> color(N);
	for (int i=0;i<N;i++) if (!chk[i]){
		grp.clear();
		dfs(i,60);
		for (auto &x : grp) color[x] = groups.size();
		groups.push_back(grp);
	}

	vector<int> push(N,-1);
	for (auto &v : groups) if (v.size() == 60){
		for (int i=0;i<60;i++) push[v[i]] = i;
	}

	for (auto &v : groups) if (v.size() != 60){
		int l = -1;
		for (auto &x : v){
			for (auto &y : graph[x]){
				if (color[x] != color[y]){
					l = y;
					break;
				}
			}
			if (l != -1) break;
		}

		grp.clear();
		for (auto &x : groups[color[l]]) chk[x] = 0;
		dfs(l,60-v.size());
		for (auto &x : groups[color[l]]) chk[x] = 1;
		vector<int> pick(60);
		for (auto &x : grp) pick[push[x]] = 1;
		for (int i=0,j=0;i<60;i++){
			if (!pick[i]){
				push[v[j]] = i;
				j++;
			}
		}
	}

	for (int i = 0; i < N; i++){
		MessageBoard(i, (X & (1ll << push[i])) > 0);
	}
}

#include "Ioi.h"
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	vector<vector<int> > graph;
	vector<vector<int> > groups;
	vector<bool> chk(N);
	vector<int> grp;

	graph.resize(N);
	for (int i=0;i<M;i++){
		graph[A[i]].push_back(B[i]);
		graph[B[i]].push_back(A[i]);
	}
	for (int i=0;i<N;i++) sort(graph[i].begin(),graph[i].end());

	function<void(int, int)> dfs;
	dfs = [&](int x, int lim){
		grp.push_back(x);
		chk[x] = 1;
		if (grp.size() == lim) return;
		for (auto &y : graph[x]) if (!chk[y]){
			dfs(y,lim);
			if (grp.size() == lim) return;
		}
	};

	vector<int> color(N);
	for (int i=0;i<N;i++) if (!chk[i]){
		grp.clear();
		dfs(i,60);
		for (auto &x : grp) color[x] = groups.size();
		groups.push_back(grp);
	}

	int cp = color[P];
	vector<int> wrote(N,-1);
	wrote[P] = V;

	vector<int> push(N,-1);
	for (auto &v : groups) if (v.size() == 60){
		for (int i=0;i<60;i++) push[v[i]] = i;
	}

	vector<int> ok(N,0);
	if (groups[cp].size() == 60){
		for (auto &x : groups[cp]) ok[x] = 1;
	}

	for (auto &v : groups) if (v.size() != 60){
		int l = -1;
		for (auto &x : v){
			for (auto &y : graph[x]){
				if (color[x] != color[y]){
					l = y;
					break;
				}
			}
			if (l != -1) break;
		}

		grp.clear();
		for (auto &x : groups[color[l]]) chk[x] = 0;
		dfs(l,60-v.size());
		for (auto &x : groups[color[l]]) chk[x] = 1;
		vector<int> pick(60);
		for (auto &x : grp) pick[push[x]] = 1;
		for (int i=0,j=0;i<60;i++){
			if (!pick[i]){
				push[v[j]] = i;
				j++;
			}
		}

		bool seen = 0;
		for (auto &x : v) if (x == P) seen = 1;
		if (seen){
			for (auto &x : v) ok[x] = 1;
			for (auto &x : grp) ok[x] = 1;
		}
	}

	function<void(int, int)> dfs2;
	for (int i=0;i<N;i++) chk[i] = 0;
	dfs2 = [&](int x, int l){
		chk[x] = 1;
		for (auto &y : graph[x]) if (y != l && ok[y] && !chk[y]){
			wrote[y] = Move(y);
			dfs2(y,x);
		}
		if (l != -1) wrote[l] = Move(l);
	};
	dfs2(P,-1);

	long long res = 0;
	for (int i=0;i<N;i++) if (ok[i]){
		res += ((long long)wrote[i]) << push[i];
	}

	return res;
}

Compilation message

Joi.cpp: In lambda function:
Joi.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (grp.size() == lim) return;
                  ^
Joi.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (grp.size() == lim) return;
                   ^

Ioi.cpp: In lambda function:
Ioi.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (grp.size() == lim) return;
                  ^
Ioi.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (grp.size() == lim) return;
                   ^

Subtask #1
8.0 / 8.0

#	결과	메모리	Grader output
1	Correct	4588 KB	Output is correct
2	Correct	4588 KB	Output is correct
3	Correct	4588 KB	Output is correct
4	Correct	4588 KB	Output is correct
5	Correct	4588 KB	Output is correct
6	Correct	4588 KB	Output is correct
7	Correct	4588 KB	Output is correct
8	Correct	4588 KB	Output is correct
9	Correct	4588 KB	Output is correct
10	Correct	4588 KB	Output is correct
11	Correct	4720 KB	Output is correct
12	Correct	4588 KB	Output is correct
13	Correct	4588 KB	Output is correct
14	Correct	4588 KB	Output is correct
15	Correct	4588 KB	Output is correct
16	Correct	4588 KB	Output is correct
17	Correct	4588 KB	Output is correct
18	Correct	4588 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	6476 KB	Output is correct
2	Correct	35 ms	6476 KB	Output is correct
3	Correct	32 ms	6476 KB	Output is correct
4	Correct	18 ms	6180 KB	Output is correct
5	Correct	18 ms	6056 KB	Output is correct
6	Correct	22 ms	6196 KB	Output is correct
7	Correct	19 ms	6196 KB	Output is correct
8	Correct	32 ms	6196 KB	Output is correct
9	Correct	18 ms	6196 KB	Output is correct
10	Correct	46 ms	7684 KB	Output is correct
11	Correct	41 ms	7684 KB	Output is correct
12	Correct	19 ms	5976 KB	Output is correct
13	Correct	15 ms	5976 KB	Output is correct
14	Correct	26 ms	5996 KB	Output is correct
15	Correct	19 ms	6164 KB	Output is correct
16	Correct	9 ms	6164 KB	Output is correct
17	Correct	19 ms	6180 KB	Output is correct
18	Correct	22 ms	6180 KB	Output is correct
19	Correct	15 ms	6180 KB	Output is correct
20	Correct	9 ms	6084 KB	Output is correct
21	Correct	3 ms	6064 KB	Output is correct
22	Correct	35 ms	6188 KB	Output is correct
23	Correct	25 ms	6188 KB	Output is correct
24	Correct	41 ms	6188 KB	Output is correct
25	Correct	32 ms	6188 KB	Output is correct
26	Correct	35 ms	6188 KB	Output is correct
27	Correct	25 ms	6188 KB	Output is correct
28	Correct	26 ms	6188 KB	Output is correct
29	Correct	32 ms	6076 KB	Output is correct
30	Correct	22 ms	6124 KB	Output is correct
31	Correct	0 ms	4588 KB	Output is correct
32	Correct	0 ms	4588 KB	Output is correct
33	Correct	0 ms	4588 KB	Output is correct
34	Correct	0 ms	4588 KB	Output is correct
35	Correct	0 ms	4588 KB	Output is correct
36	Correct	0 ms	4588 KB	Output is correct
37	Correct	0 ms	4588 KB	Output is correct
38	Correct	0 ms	4588 KB	Output is correct
39	Correct	0 ms	4588 KB	Output is correct
40	Correct	0 ms	4588 KB	Output is correct
41	Correct	0 ms	4588 KB	Output is correct
42	Correct	0 ms	4588 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4588 KB	Output is correct
2	Correct	0 ms	4588 KB	Output is correct
3	Correct	0 ms	4588 KB	Output is correct
4	Correct	0 ms	4852 KB	Output is correct
5	Correct	0 ms	4852 KB	Output is correct
6	Correct	0 ms	4852 KB	Output is correct
7	Correct	0 ms	4852 KB	Output is correct
8	Correct	0 ms	4852 KB	Output is correct
9	Correct	12 ms	6064 KB	Output is correct
10	Correct	12 ms	6064 KB	Output is correct
11	Correct	9 ms	6064 KB	Output is correct
12	Correct	0 ms	4588 KB	Output is correct
13	Correct	0 ms	4588 KB	Output is correct
14	Correct	0 ms	4588 KB	Output is correct
15	Correct	0 ms	4588 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	6316 KB	Output is correct
2	Correct	38 ms	6476 KB	Output is correct
3	Correct	52 ms	6484 KB	Output is correct
4	Correct	18 ms	6180 KB	Output is correct
5	Correct	18 ms	6056 KB	Output is correct
6	Correct	27 ms	6196 KB	Output is correct
7	Correct	38 ms	6196 KB	Output is correct
8	Correct	26 ms	6196 KB	Output is correct
9	Correct	28 ms	6196 KB	Output is correct
10	Correct	55 ms	7684 KB	Output is correct
11	Correct	48 ms	7684 KB	Output is correct
12	Correct	12 ms	5976 KB	Output is correct
13	Correct	15 ms	5944 KB	Output is correct
14	Correct	18 ms	6020 KB	Output is correct
15	Correct	18 ms	6164 KB	Output is correct
16	Correct	18 ms	6164 KB	Output is correct
17	Correct	15 ms	6180 KB	Output is correct
18	Correct	28 ms	6180 KB	Output is correct
19	Correct	22 ms	6180 KB	Output is correct
20	Correct	12 ms	6084 KB	Output is correct
21	Correct	12 ms	6064 KB	Output is correct
22	Correct	32 ms	6188 KB	Output is correct
23	Correct	35 ms	6188 KB	Output is correct
24	Correct	36 ms	6188 KB	Output is correct
25	Correct	36 ms	6188 KB	Output is correct
26	Correct	19 ms	6188 KB	Output is correct
27	Correct	26 ms	6188 KB	Output is correct
28	Correct	26 ms	6188 KB	Output is correct
29	Correct	15 ms	6076 KB	Output is correct
30	Correct	26 ms	6124 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	6468 KB	Output is correct
2	Correct	35 ms	6468 KB	Output is correct
3	Correct	35 ms	6476 KB	Output is correct
4	Correct	49 ms	6180 KB	Output is correct
5	Correct	22 ms	6080 KB	Output is correct
6	Correct	58 ms	6196 KB	Output is correct
7	Correct	32 ms	6196 KB	Output is correct
8	Correct	28 ms	6196 KB	Output is correct
9	Correct	34 ms	6196 KB	Output is correct
10	Correct	41 ms	7684 KB	Output is correct
11	Correct	49 ms	7684 KB	Output is correct
12	Correct	18 ms	5976 KB	Output is correct
13	Correct	12 ms	5976 KB	Output is correct
14	Correct	12 ms	5996 KB	Output is correct
15	Correct	15 ms	6164 KB	Output is correct
16	Correct	15 ms	6164 KB	Output is correct
17	Correct	15 ms	6172 KB	Output is correct
18	Correct	28 ms	6180 KB	Output is correct
19	Correct	26 ms	6180 KB	Output is correct
20	Correct	12 ms	6084 KB	Output is correct
21	Correct	12 ms	6064 KB	Output is correct
22	Correct	35 ms	6188 KB	Output is correct
23	Correct	62 ms	6188 KB	Output is correct
24	Correct	32 ms	6188 KB	Output is correct
25	Correct	28 ms	6188 KB	Output is correct
26	Correct	38 ms	6188 KB	Output is correct
27	Correct	22 ms	6188 KB	Output is correct
28	Correct	32 ms	6188 KB	Output is correct
29	Correct	32 ms	6076 KB	Output is correct
30	Correct	28 ms	6124 KB	Output is correct
31	Correct	0 ms	4588 KB	Output is correct
32	Correct	0 ms	4588 KB	Output is correct
33	Correct	0 ms	4588 KB	Output is correct
34	Correct	0 ms	4588 KB	Output is correct
35	Correct	0 ms	4588 KB	Output is correct
36	Correct	0 ms	4588 KB	Output is correct
37	Correct	0 ms	4588 KB	Output is correct
38	Correct	0 ms	4588 KB	Output is correct
39	Correct	0 ms	4588 KB	Output is correct
40	Correct	0 ms	4588 KB	Output is correct
41	Correct	0 ms	4588 KB	Output is correct
42	Correct	0 ms	4588 KB	Output is correct

답안 #26603

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 55.0 / 55.0

Subtask #5 17.0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
55.0 / 55.0

Subtask #5
17.0 / 17.0