글 읽기 - 12501 채점이 이상합니다.

showx123 4년 전 0

코드잼에서 정답인 코드가, 백준에서는 오답으로 뜹니다.
#include <stdio.h>
#include <memory.h>
#include <vector>
#include <set>

using namespace std;

int N, M;

int ans;

int graph[2005][2005];
int s[2005];
int e[2005];
int color[2005];

#define MAX 54321

int abs(int num) {
	if (num < 0)
		return num * -1;
	else
		return num;
}

int is_edge(int s, int e) {
	if (abs(s - e) == 1 || abs(s - e) == N - 1)
		return 1;
	else
		return 0;
}

int decrement(int v) {
	if (v == 1)
		return N;
	else
		return v - 1;
}

int increment(int v) {
	if (v == N)
		return 1;
	else
		return v + 1;
}

int find(int origin, int cur, int next, int depth, vector<int> &list) {
	if (graph[cur][next] == 2 && is_edge(cur, next))
		return MAX;
	else if (graph[cur][next] == 3 && !is_edge(cur, next))
		return MAX;

	//printf("%d %d %d %d\n", origin, cur, next, depth);

	graph[cur][next]++;
	graph[next][cur]++;
 
	list.push_back(next);
	if (next == origin) {
		return depth;
	}

	for (int i = decrement(origin);  ; i = decrement(i)) {
		if (i == cur)
			continue;

		if (graph[next][i] || is_edge(next, i) || i == origin) {
			//list.push_back(i);
			 return find(origin, next, i, depth + 1, list);
		}
	}

	//should not reach here
	return MAX;
}

int inc_color(int color) {
	if (color == ans)
		return 1;
	else
		return color + 1;
}

int dec_color(int color) {
	if (color == 1)
		return ans;
	else
		return color - 1;
}

int not_neighbor_color(int prev, int next) {
	if (prev == 0 && next == 0)
		return 1;

	if (prev == 0)
		return inc_color(next);

	if (next == 0)
		return inc_color(prev);
	
	if (prev == next)
		return inc_color(prev);

	if (inc_color(prev) == next)
		return inc_color(next);

	if (inc_color(next) == prev)
		return inc_color(prev);

	return inc_color(prev);
}

void find_clockwise(int origin, int next, vector<int> &list) {
	if (origin > next) {
		int temp = origin;
		origin = next;
		next = temp;
	}

	if (decrement(origin) == next) {
		int temp = origin;
		origin = next;
		next = temp;
	}

	list.push_back(origin);
	list.push_back(next);



	int cur = next;
	for (int i = decrement(origin); ; i = decrement(i)) {
		if (i == cur)
			return;

		if (is_edge(i, cur) || graph[cur][i]) {
			if (i == origin)
				break;

			cur = i;
			list.push_back(i);
			i = increment(origin);
		}
	}
}

int find_counter_clockwise(int origin, int next, vector<int> &list) {
	if (is_edge(origin, next))
		return 0;

	if (origin < next) {
		int temp = origin;
		origin = next;
		next = temp;
	}

	list.push_back(origin);
	list.push_back(next);

	int cur = next;
	for (int i = decrement(origin); ; i = decrement(i)) {
		if (i == cur)
			return 1;

		if (is_edge(i, cur) || graph[cur][i]) {
			if (i == origin)
				break;

			cur = i;
			list.push_back(i);
			i = increment(origin);
		}
	}

	return 1;
}
int cnt;
void set_room(vector<int> list) {
	int start = 0;
	int start_color = 1; 
	int i;


	int size = list.size();
	set<int> color_set;
	vector<int> not_used;

	if (size < 3)
		return;

	//printf("room : ");
	//for (i = 0; i < size; i++) {
	//	printf("%d ", list[i]);
	//}
	//printf("\n");
	//return;

	int check = 0;
	for (i = 0; i < size; i++) {
		if (color[list[i]]) {
			color_set.insert(color[list[i]]);
			check++;
		}
	}

	if (check == 0) {
		cnt++;
		if (cnt > 1)
			printf("something wrong!\n");
	}

	// already colored
	if (check == size)
		return;

	if (check > 2) {
		printf("check : %d something wrong!\n",check);
		
	}


	for (i = 1; i <= ans; i++) {
		if (color_set.find(i) == color_set.end())
			not_used.push_back(i);
	}

	if (not_used.size() < ans - 2)
		printf("size : %d not_used size : %d something wrong!\n", size, not_used.size());

	vector<int>::iterator iter = not_used.begin();
	for (i = 0; i < size; i++) {
		if (color[list[i]])
			continue;

		if (iter != not_used.end())	{
			color[list[i]] = *iter;
			iter++;
		}
		else {
			if(i==0)
				color[list[i]] = not_neighbor_color(color[list[size-1]], color[list[(i + 1) % size]]);
			else
				color[list[i]] = not_neighbor_color(color[list[i-1]], color[list[(i + 1) % size]]);
		}
	}

	for (i = 0; i < size; i++) {
		int prev = list[i];
		int next = list[(i + 1) % size];
		vector<int> temp_list;
		vector<int> temp_list2;

		find_clockwise(prev, next, temp_list);
		set_room(temp_list);

		find_counter_clockwise(prev, next, temp_list2);
		set_room(temp_list2);
	}
		
	return;	
}

int visit[2005];

void set_color(int vertex) {
	int i;

	if (visit[vertex])
		return;

	visit[vertex] = 1;

	for (i = vertex + 1; i <= N; i++) {
		if (graph[vertex][i] || is_edge(vertex, i)) {
			vector<int> list;
			find_clockwise(vertex, i, list);
			set_room(list);

			list.clear();
			find_counter_clockwise(vertex, i, list);
			set_room(list);


			return;
			//vector<int> list;
			//find_clockwise(vertex, i, list);

			//printf("room clockwise %d %d : ", vertex, i);
			//for (int j = 0; j < list.size(); j++) {
			//	printf("%d ", list[j]);
			//}
			//printf("\n");

			//list.clear();
			//find_counter_clockwise(vertex, i, list);

			//printf("room counter_clockwise %d %d : ", vertex, i);
			//for (int j = 0; j < list.size(); j++) {
			//	printf("%d ", list[j]);
			//}
			//printf("\n");
		}
	}

	for (i = 1; i <= N; i++) {
		if (graph[vertex][i] && visit[i] == 0)
			set_color(i);
	}
}


int main(void) {
	int t, T;
	int i, j;

	scanf("%d", &T);

	for (t = 1; t <= T; t++) {
		ans = MAX;
		memset(graph, 0, sizeof(graph));
		memset(color, 0, sizeof(color));
		memset(visit, 0, sizeof(visit));
		cnt = 0;

		scanf("%d%d", &N, &M);

		for (i = 0; i < M; i++) {
			scanf("%d", &s[i]);
		}
		for (i = 0; i < M; i++) {
			scanf("%d", &e[i]);
			graph[s[i]][e[i]] = 1;
			graph[e[i]][s[i]] = 1;
		}


		for (i = 1; i <= N; i++) {
			for (j = 1; j <= N; j++) {
				if (graph[i][j]) {
					vector<int> temp_list;
					vector<int> temp_list2;

					find_clockwise(i, j, temp_list);
					if (temp_list.size() < ans)
						ans = temp_list.size();

					find_counter_clockwise(i, j, temp_list2);
					if (temp_list2.size() < ans)
						ans = temp_list2.size();
				}
			}
		}



		for (i = 0; i < M; i++) {
			graph[s[i]][e[i]] = 1;
			graph[e[i]][s[i]] = 1;
		}


		set_color(1);

		printf("Case #%d: %d\n", t, ans);

		for (i = 1; i <= N; i++)
			printf("%d ", color[i]);

		printf("\n");
	}
} 
evenharder 4년 전 0

BOJ에 있는 코드잼 문제에서 흔히 일어나는 슬픈 일입니다. 스페셜 저지가 없기 때문입니다...
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

12501 채점이 이상합니다.

showx123 4년 전 0

evenharder 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
