글 읽기 - 왜 메모리초과가 나는지 모르겠습니다

mc_progw12 3년 전 0

bfs로 하면 visit를 써야하는 반례를 모르겠어서 visit 배열은 쓰지 않았습니다.

혹시 visit를 쓰지 않으면 안되는 케이스가 있을까요?

' 1->2 2->3 3->4 4->5 5->2 ' 이런 경우 밖에 없을 것 같은데 애초에 불가능한 경우이니 반례가 없을 것 같은데요..

#include <bits/stdc++.h>


using namespace std;



int t,n,k;
vector<int> v[1001];
int d[1001];
int u[1001];

int parent(int u, int a[]){
    while(a[u] != u){
        u = a[u];
    }
    return u;
}

int f(int s, int e){
    int m=0;
    queue< pair<int, int> > q;

    q.push({s,0});
    while(!q.empty()){
        int qf = q.front().first;
        int qs = q.front().second;

        if(qf == e) m = max(m,qs); // end를 만날 때마다 최댓값을 찾아줍니다
                                   // end에 마지막에 도달하는 경우가 답입니다
        for(int x : v[qf]){
            q.push({x,qs+d[qf]});
        }

        q.pop();
    }

    return m+d[e];
}

int main()
{
    cin >> t;
    for(; t; t--){
        memset(d,0,sizeof(d));
        memset(u,0,sizeof(u));
        for(int i=1;i<=1000;i++) v[i].clear();
        int p1,p2;

        cin >> n >> k;
        for(int i=1;i<=n;i++){
            cin >> d[i];
            u[i] = i;
        }
        for(int i=1;i<=k;i++){ // 유니온파인드로 병합하다보면 u[1]=u[2]=u[3]...u[n] = k가
            cin >> p1 >> p2; // 될 것인데 그 때 그 k가 루트라고 생각했습니다
            v[p1].push_back(p2);

            u[parent(p2,u)] = parent(p1,u);
        }

        int s = parent(1,u);
        int e; cin >> e;

        printf("%d\n",f(s,e));
    }
}

mc_progw12 3년 전 0

아하 알아냈습니다

1->2 1->3 2->4 3->4 이런 꼴이 계속 반복된다면 결국 2의 지수 꼴로 경우의 수가 만들어져서 그런거였군요

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

문제

문제

출처

ICPC

왜 메모리초과가 나는지 모르겠습니다

mc_progw12 3년 전 0

mc_progw12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말