글 읽기 - 어떤 부분에서 시간초과가 일어나는지 알고 싶습니다.

(追記) (追記ここまで)

어떤 부분에서 시간초과가 일어나는지 알고 싶습니다.

9466번 - 텀 프로젝트

bjcho1503 1년 전 0

나름대로 시간초과가 날거 같은 부분은 다 막았다고 생각하는데, 33% 쯤에서 시간초과가 발생합니다.

가장 의심되는 부분은 배열을 초기화 하는 부분인데.. 정확히 어떤 부분에서 시간초과가 일어나는 것인지 알고 싶습니다.

도움 주시면 감사하겠습니다..!

#include <iostream>
#include <vector>
#include <map>
using namespace std;
bool jo[100001] = {false,}, ro[100001] = {false,};
vector<int> ar = {0}, re = {0};
int dfs(int pr, map<int, bool> lo) {
 ro[pr] = true;
 lo[pr] = true;
 if (lo[ar[pr]]) {
 jo[pr] = true;
 return ar[pr];
 }
 if (jo[ar[pr]] || ro[ar[pr]]) return -1;
 int rot = dfs(ar[pr], lo);
 if (lo[rot]) {
 jo[pr] = true;
 return rot;
 }
 return -1;
}
int main() {
 ios::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr);
 int t;
 cin >> t;
 while (t--) {
 int res = 0, n;
 cin >> n;
 for(int i = 0; i < n; i++) cin >> ar.emplace_back();
 for(int i = 1; i <= n; i++) {
 if (jo[i] || ro[i]) continue;
 map<int, bool> a;
 dfs(i, a);
 }
 for(int i = 1; i <= n; i++) if (!jo[i]) res++;
 cout << res << "\n";
 ar = re;
 for (int i = 1; i < 100001; i++) ro[i] = jo[i] = false;
 }
}

wnwoghd22 1년 전 1

map을 참조자로 넘기지 않은 부분이 의심스럽읍니다

bjcho1503 1년 전 0

@wnwoghd22 조언 감사합니다!
말씀 해주신대로 map을 참조자로 넘기고, dfs부분에서 return 직전에 map에 pr의 값을 false로 바꾸는 작업을 진행하니 풀렸습니다.

좋은하루 보내세요 :)

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

어떤 부분에서 시간초과가 일어나는지 알고 싶습니다.

bjcho1503 1년 전 0

wnwoghd22 1년 전 1

bjcho1503 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말