글 읽기 - 신기한 현상을 발견했습니다.

jihookang 2년 전 0

1번 코드는 맞았습니다, 2번 코드는 1%에서 시간초과가 뜹니다.

네트워크에 유량을 흘려주는 순서만 바꿨을 뿐인데 왜 이런 현상이 나타나는지 궁금합니다.

//1
#include<bits/stdc++.h>
using namespace std;
#pragma gcc optimize("03");
#pragma gcc optimize("0fast");
#pragma gcc optimize("unroll-loops");
int N, M, cnt, j, ans;
bool ad[1009][1009];
vector<bool> vst;
vector<int> bmate;
bool dfs(int cur) {
	if (vst[cur]) return 0;
	vst[cur] = 1;
	for (int nxt = 1; nxt <= M; nxt++) if (ad[cur][nxt]) {
		if (!bmate[nxt] || dfs(bmate[nxt])) {
			bmate[nxt] = cur;
			return 1;
		}
	}
	return 0;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> cnt;
		while (cnt--) {
			cin >> j;
			ad[i][j] = 1;
		}
	}
	bmate = vector<int>(M + 1, 0);
    
    //다른 부분
	for (int i = 1; i <= N; i++) {
		vst = vector<bool>(N + 1, 0);
		if (dfs(i)) ans++;
		vst = vector<bool>(N + 1, 0);
		if (dfs(i)) ans++;
	}
    //다른 부분
    
	cout << ans;
}





//2
#include<bits/stdc++.h>
using namespace std;
#pragma gcc optimize("03");
#pragma gcc optimize("0fast");
#pragma gcc optimize("unroll-loops");
int N, M, cnt, j, ans;
bool ad[1009][1009];
vector<bool> vst;
vector<int> bmate;
bool dfs(int cur) {
	if (vst[cur]) return 0;
	vst[cur] = 1;
	for (int nxt = 1; nxt <= M; nxt++) if (ad[cur][nxt]) {
		if (!bmate[nxt] || dfs(bmate[nxt])) {
			bmate[nxt] = cur;
			return 1;
		}
	}
	return 0;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> cnt;
		while (cnt--) {
			cin >> j;
			ad[i][j] = 1;
		}
	}
	bmate = vector<int>(M + 1, 0);
    
    //다른 부분
	for (int i = 1; i <= N; i++) {
		vst = vector<bool>(N + 1, 0);
		if (dfs(i)) ans++;
	}
    for (int i = 1; i <= N; i++) {
		vst = vector<bool>(N + 1, 0);
		if (dfs(i)) ans++;
	}
    //다른 부분
    
	cout << ans;
}

kdh6429 2년 전 1

안된다고 하는 방식으로 제코드 수정해서 돌려봤는데 잘 통과되네요.

다른 부분이 문제인것같은데.. 그거까진 잘 못찾겠네요 ^^;

https://www.acmicpc.net/source...

jihookang 2년 전 1

kdh6429님 코드랑 제 코드랑 거의 똑같은데 이상하네요...

kdh6429님은 인접 리스트를 쓰셨고, 저는 인접 행렬을 쓴 부분만 다른 것 같아서 아래처럼 인접 리스트로 바꾸어서 제출해보았습니다.

그랬더니 여전히 시간초과가 뜨네요...ㅠㅠ

1%에서 33%로 조금 나아지기는 했습니다.

이 문제에서는 인접리스트나 인접 행렬이나 시간복잡도가 동일할 것 같은데 어디가 문제일까요.....

#include<bits/stdc++.h>
using namespace std;
#pragma gcc optimize("03");
#pragma gcc optimize("0fast");
#pragma gcc optimize("unroll-loops");
#define pb push_back
int N, M, cnt, j, ans;
vector<bool> vst;
vector<int> bmate, ad[1009];
bool dfs(int cur) {
	if (vst[cur]) return 0;
	vst[cur] = 1;
	for (int nxt : ad[cur]) {
		if (!bmate[nxt] || dfs(bmate[nxt])) {
			bmate[nxt] = cur;
			return 1;
		}
	}
	return 0;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> cnt;
		while (cnt--) {
			cin >> j;
			ad[i].pb(j);
		}
	}
	bmate = vector<int>(M + 1, 0);

	for (int i = 1; i <= N; i++) {
		vst = vector<bool>(N + 1, 0);
		if (dfs(i)) ans++;
	}
	for (int i = 1; i <= N; i++) {
		vst = vector<bool>(N + 1, 0);
		if (dfs(i)) ans++;
	}

	cout << ans;
}

kdh6429 2년 전 1

vst 변수를 array 로 변경하고 memset으로 초기화 하니까 통과되네요. 아마 매번 vector 를 재생성하는 비용이 비싼가 봅니다. fill 이나 assign 으로 초기화는 안해봤습니다.

jihookang 2년 전 0

오 감사합니다. 덕분에 배워갑니다!

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

문제

문제

출처

ICPC

신기한 현상을 발견했습니다.

jihookang 2년 전 0

kdh6429 2년 전 1

jihookang 2년 전 1

kdh6429님 코드랑 제 코드랑 거의 똑같은데 이상하네요...

kdh6429님은 인접 리스트를 쓰셨고, 저는 인접 행렬을 쓴 부분만 다른 것 같아서 아래처럼 인접 리스트로 바꾸어서 제출해보았습니다.

그랬더니 여전히 시간초과가 뜨네요...ㅠㅠ

1%에서 33%로 조금 나아지기는 했습니다.

이 문제에서는 인접리스트나 인접 행렬이나 시간복잡도가 동일할 것 같은데 어디가 문제일까요.....

kdh6429 2년 전 1

jihookang 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말