Submission #26603

#	Time	Username	Problem	Language	Result	Execution time	Memory
26603		kriii	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	62 ms	7684 KiB

Joi

#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);
	}
}

Ioi

#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 (stderr)

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 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17