글 읽기 - 시간초과가 대체 어떻게 나는지 모르겠습니다 ㅠㅠ

mozzi01331 3년 전 0

초기화는 다 해주고 있고, 딱히 for loop의 범위가 잘못된 것도 없는 것 같은데 대체 왜 시간 초과가 발생할까요ㅠㅠ?
입출력으로 printf, scanf도 사용하고 있는데 딱히 어떤 부분이 문제가 되는 건지 잘 모르겠습니다 ㅠㅠ

#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;


int m, n;
int parent[200020];
vector<vector<int>> costs;

bool compare(vector<int> a, vector<int> b){
    return a[2] < b[2];
}

int find(int n){
    if(parent[n] == n) return n;
    else{
        return parent[n] = find(parent[n]);
    }
}

int main(){
    int i, m, n, ans, totalcost;
    int a, b, c;
    while(true){
        scanf("%d %d", &m, &n);
        if(m == 0 && n == 0) break;
        ans = 0;
        totalcost = 0;
        costs.clear();
        for(i=0;i<m;i++) parent[i] = i;
        for(i=0;i<n;i++){
            //printf("in tc, the ith idx is %d\n", i);
            scanf("%d %d %d", &a, &b, &c);
            costs.push_back({a, b, c});
        }
    
        sort(costs.begin(), costs.end(), compare);
    
        for(i=0;i<costs.size();i++){
            int roota = find(costs[i][0]);
            int rootb = find(costs[i][1]);
        
            if(roota != rootb){
                parent[roota] = parent[rootb];
                ans += costs[i][2];
            }
            totalcost += costs[i][2];
        }
        printf("%d\n", totalcost - ans);
    }
    return 0;
}

prarie 3년 전 0

45번째 줄에 합치는 연산에 오류가 있는 것 같은데 한번 다시 짜보시겠어요?

다른 점은 모르겠네요

mozzi01331 3년 전 0

parent[roota] = rootb로 수정했지만 여전히 시간초과가 발생하고 있습니다ㅠㅠ 말씀하신 내용이 이 부분이 맞으실까요? @prarie

prarie 3년 전 0

그렇게 수정하시고 12번째 줄을

bool compare(vector &a, vector &b){
return a[2] < b[2];
}

와 같이 & 를 붙여보고 한번 제출해보세요

이렇게 하니까 되긴 되는데, 저도 C++은 잘 몰라서 정확하지 않을 수 있습니다

& 를 붙이면 값을 복사하지 않고 변수 명에 이름을 새롭게 붙이는거라 좀 더 빠를 수 있습니다.

prarie 3년 전 0

아 그리고 45번째 줄에는 오류가 없는 것 같네요

find 연산을 미리 하신걸 못봤어요

mozzi01331 3년 전 0

@prarie 와 정말 reference값으로 바꾸니까 바로 해결되는 것을 발견했습니다 ㅠㅠ 사소한 거라고 생각했는데 엄청 중요한 부분이었네요.. 감사합니다!

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

문제

문제

출처

ICPC

시간초과가 대체 어떻게 나는지 모르겠습니다 ㅠㅠ

mozzi01331 3년 전 0

prarie 3년 전 0

mozzi01331 3년 전 0

prarie 3년 전 0

prarie 3년 전 0

mozzi01331 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말