글 읽기 - 9466 텀프로젝트 TLE

exqt 8년 전 0

한 80%쯤에서 TLE 나오는데

아슬아슬하게 1초 넘어가는지 아니면 무한재귀 도는것인지 잘 모르겠습니다

https://icpcarchive.ecs.baylor.edu/index.php?optio...

참고로 여기서 제출하면 0.2초에 AC나오네요

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
 
int d[100010];
int s[100010]; // 0:unknown 1:yes 2:no
int visit[100010];
int b = 0; 
 
int go(int id, int o)
{
    if(visit[id]) {b = id; return 1;}
    if(id == o) return 1;
    if(s[id] == 1) return 2;
    if(id == d[id]) return 2;
 
    visit[id] = 1;
    s[id] = go(d[id], o);
    visit[id] = 0;
 
    if(b == id) {return 2;}
    return s[id];
}
 
int main()
{
    int tc; scanf("%d", &tc);
    while(tc--)
    {
        int n; scanf("%d", &n);
        for(int i=1; i<=n; i++)  scanf("%d", &d[i]);
        for(int i=1; i<=n; i++) s[i] = 0;
 
        for(int i=1; i<=n; i++) {
            b = 0;
            if(!s[i]) s[i] = go(d[i], i);
        }
 
        int res = 0;
        for(int i=1; i<=n; i++) {
            if(s[i] == 2) res++;
        }
 
        printf("%d\n", res);
    }
 
    return 0;
}

koosaga 8년 전 1

n^2네요!

koosaga 8년 전 0

원래 live archive 데이터는 약합니다.

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

문제

문제

출처

ICPC

9466 텀프로젝트 TLE

exqt 8년 전 0

koosaga 8년 전 1

koosaga 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말