글 읽기 - 반례를 알고 싶습니다.

jaeyoon8783 4년 전 0

scc를 활용하기 전에 원시적으로 비트마스크를 사용하여 해봤습니다. 특히 0일때의 case를 많이 생각해보았지만 발견하지 못하였습니다.

도움을 받고 싶습니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;




int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int v, e;
	cin >> v >> e;
	pair<int, int>  p[100];
	for (int i = 0; i < e; i++)
	{
		cin >> p[i].first >> p[i].second;
	}

	
	for (int i = 0; i < (1 << v); i++)    // 0이면 1<<0 false  1<<1 false 1<<2 false << 1<<3 false.... 
	{
		int j = 0;
		for (j ; j < e; j++)
		{
			if (p[j].first > 0 && p[j].second > 0)
			{
				if ( (((1 << p[j].first - 1) & i) == 0) && (((1 << p[j].second - 1) & i) == 0)) // -1한 이유는 1이 1<<0이기 때문이고 2는 1<< 1이기 때문이다.
					break;
			}
			else if (p[j].first < 0 && p[j].second > 0)
			{
				if ( (((1 << (-1 * p[j].first) - 1) & i) == 1) && (((1 << p[j].second - 1) & i) == 0))
					break;
			}
			else if (p[j].first > 0 && p[j].second < 0)
			{
				if ((((1 << p[j].first - 1) & i) == 0) && (((1 << (-1 * p[j].second) - 1) & i) == 1))
					break;
			}
			else
			{
				if ((((1 << (-1 * p[j].first) - 1) & i) == 1) && (((1 << (-1 * p[j].second) - 1) & i) == 1))
					break;
			}
		}

		if (j == e)
		{
			cout << 1;
			return 0;
		}
	}
	cout << 0;

}

jaeyoon8783 4년 전 0

p[j].first 나 second 가 <0 일때 (((1 << (-1 * p[j].first) - 1) & i) == 1) 이 아니라 (((1 << (-1 * p[j].first) - 1) & i) != 0 ) 으로 해야 한다는것을 깨달았습니다....

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 알고 싶습니다.

jaeyoon8783 4년 전 0

jaeyoon8783 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말