글 읽기 - 배열로 하면 맞는데 동적배열로하면 95%에서 런타임에러가 나네요

dmlgus322 5년 전 0

어찌저찌해서 답은 맞췄는데 G, stat, isCycle, numOfColor 를 배열로 구현할 때는 맞췄지만 벡터로 구현할 때는 런타임에러가 납니다.

1~99번째 라인이 맞은답이고 그 이후가 틀린답입니다. 어떤부분에서 문제가 나는건지 궁금합니다!

///맞은 답

#include <cstdio>
#include <vector>

using namespace std;
typedef enum __Status {
    IS_NOT_VISITED,
    IS_VISITING,
    IS_VISITED
}Status;
int G[1000001];
Status stat[1000001];
bool isCycle[1000001];
long long int numOfColor[1000001];
int N;
long long int K;
long long int lmod = 1000000007LL;
long long int answer = 1;
void DFS(int i);
int main(void)
{
    scanf("%d %lld", &N, &K);
    
    //init graph G
    for (int i = 1; i <= N; i++) {
        scanf("%d", &G[i]);
    }
    
    //init stat
    for (int i = 1; i <= N; i++) {
        stat[i] = IS_NOT_VISITED;
    }
    
    //init isCycle
    for (int i = 1; i <= N; i++) {
        isCycle[i] = false;
    }
    
    //init numOfColor
    
    numOfColor[1] = K;
    numOfColor[2] = (K * (K - 1)) % lmod;
    numOfColor[3] = (numOfColor[2] * (K - 2)) % lmod;
    for (int i = 4; i <= N; i++){
        numOfColor[i] = (K - 1) * numOfColor[i - 2];
        numOfColor[i] += (K - 2) * numOfColor[i - 1];
        numOfColor[i] %= lmod;
    }

    
    
    // DFS search (cycle)
    for (int i = 1; i <= N; i++) {
        if(stat[i] == IS_NOT_VISITED)
            DFS(i);
    }
    
   
    for (int i = 1; i <= N; i++) {
        if(!isCycle[i]){
            answer *= K-1;
            answer %= lmod;
        }
    }
    
    printf("%lld\n", answer);
    return 0;
    
}


void DFS(int i)
{
    stat[i] = IS_VISITING;
    int cur_i = G[i];
    if(stat[cur_i] == IS_NOT_VISITED)
    {
        DFS(cur_i);
    }
    else if (stat[cur_i] == IS_VISITING){
        int cnt = 0;
        for (int x = cur_i; x != i; x = G[x]) {
            isCycle[x] = true;
            cnt++;
            
        }
        isCycle[i] = true;
        cnt++;
        answer *= numOfColor[cnt];
        answer %= lmod;
    //    printf("answer : %lld\n", answer);
    }

    stat[i] = IS_VISITED;
}


////////////////////////////////////////////////////////////
//틀린 답 (95%에서 런타임 에러)

#include <cstdio>
#include <vector>

using namespace std;
typedef enum __Status {
    IS_NOT_VISITED,
    IS_VISITING,
    IS_VISITED
}Status;
vector<int> G;
vector<Status> stat;
vector<bool> isCycle;
vector<long long int> numOfColor;
int N;
long long int K;
long long int lmod = 1000000007LL;
long long int answer = 1;
void DFS(int i);
int main(void)
{
    scanf("%d %lld", &N, &K);
    G.resize(N+1);
    stat.resize(N+1);
    isCycle.resize(N+1);
    numOfColor.resize(N+1);
    
    //init graph G
    for (int i = 1; i <= N; i++) {
        scanf("%d", &G[i]);
    }
    
    //init stat
    for (int i = 1; i <= N; i++) {
        stat[i] = IS_NOT_VISITED;
    }
    
    //init isCycle
    for (int i = 1; i <= N; i++) {
        isCycle[i] = false;
    }
    
    //init numOfColor
    
    numOfColor[1] = K;
    numOfColor[2] = (K * (K - 1)) % lmod;
    numOfColor[3] = (numOfColor[2] * (K - 2)) % lmod;
    for (int i = 4; i <= N; i++){
        numOfColor[i] = (K - 1) * numOfColor[i - 2];
        numOfColor[i] += (K - 2) * numOfColor[i - 1];
        numOfColor[i] %= lmod;
    }

    
    
    // DFS search (cycle)
    for (int i = 1; i <= N; i++) {
        if(stat[i] == IS_NOT_VISITED)
            DFS(i);
    }
    
   
    for (int i = 1; i <= N; i++) {
        if(!isCycle[i]){
            answer *= K-1;
            answer %= lmod;
        }
    }
    
    printf("%lld\n", answer);
    return 0;
    
}


void DFS(int i)
{
    stat[i] = IS_VISITING;
    int cur_i = G[i];
    if(stat[cur_i] == IS_NOT_VISITED)
    {
        DFS(cur_i);
    }
    else if (stat[cur_i] == IS_VISITING){
        int cnt = 0;
        for (int x = cur_i; x != i; x = G[x]) {
            isCycle[x] = true;
            cnt++;
            
        }
        isCycle[i] = true;
        cnt++;
        answer *= numOfColor[cnt];
        answer %= lmod;
    //    printf("answer : %lld\n", answer);
    }

    stat[i] = IS_VISITED;
}

djm03178 5년 전 1

44번째 줄이 항상 안전함이 보장될까요?

dmlgus322 5년 전 0

K가 1일때 말씀이신가요? 43번째줄에서 0이 나와서 문제없을것같은데요... 그리고 위쪽말고 밑에 코드(100줄 밑)가 런타임 에러 난 코드입니다!

djm03178 5년 전 1

147줄에도 똑같은 문장이 있습니다. 이 문장이 과연 안전할까요? 예를 들어 N=1이면 numOfColor의 크기는 2가 될 텐데, 3이라는 인덱스가 존재할까요?

dmlgus322 5년 전 0

아 정말 감사합니다...!

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

문제

문제

출처

ICPC

배열로 하면 맞는데 동적배열로하면 95%에서 런타임에러가 나네요

dmlgus322 5년 전 0

djm03178 5년 전 1

dmlgus322 5년 전 0

djm03178 5년 전 1

dmlgus322 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말