Codeforces Round 998 (feat. Python)

개요

이렇게 갑자기 글을 쓰는 이유는 믿을 수 없는 일을 당했기 때문인데…

난 “파이썬 당한다”는 말이 시간초과만 해당되는줄 알았다.

근데 런타임 에러로 당하는건 너무 새로운 충격이라 글을 쓸 수밖에 없었다.

문제의 E번인데 path를 잘못 이해해서 헤맨건 그렇다 치고…

유니온 파인드로 연결 요소를 찾아가면서 G그래프와 똑같이 만들면 되는 문제인데, 아무리 코드를 뜯어고쳐도 계속 테스트 4번에서 런타임 에러가 났다. 메모리 초과라고 뜨는 것도 아니라 대체 뭐가 문제인지 모르겠다.

결국 풀이에 실패하고, 아무래도 레이팅이 또 왕창 깎일 예정인데………….

글쎄 대회 끝나고 1분쯤 뒤에 혹시나 싶어서 gpt에게 C++ 코드로 바꿔달라고 요청했고, AC를 받았다.

이것만 맞췄으면 레이팅 유지는 되는거였는데, 더 슬픈건 아직도 이유를 모르겠다. 재귀 깊이 문제인가 싶어서 최대 정점 개수보다 더 깊게 설정도 해보고, Union-Find 연산에서 범위 검사도 해보고, 하여튼 생각나는 짓은 다 했는데 이렇게 허무한 이유로…?

억울해서 미칠 것 같은데 이게 파이썬 힙스터의 운명이라 생각하면 그냥 받아들일만 한 것 같기도 하… 지 않다.

최근 코포는 바닥 밑에는 더 바닥이 있다는 것만 증명하는 장이 되는 것 같아서 속이 쓰리다.

그러나 깨달음을 얻은 것도 있다. (이제서야?)

앞으로 코포에 제출할 때는 gpt의 도움을 받더라도 A, B번 말고는 다 C++로 제출하는 게 속이 편할 것 같다. 안 그러면 진짜 홧병나서 돌아가신다.

그리고 C++ 공부를 진짜 진짜 시작할 때가 된 것 같다. 이제서야 필요성을 느끼는 것도 웃기긴 한데 SUAPC도 얼마 안 남았고 이렇게 살다간 제 명에 못 죽을 것 같다.

혹시 이유를 아는 고수님이 있다면 제발 도와주세요…

아 코포 계정 삭제하고싶어;;;

코드

파이썬 버전

import sys
from math import ceil, log

input = sys.stdin.readline
sys.setrecursionlimit((10 ** 5) * 2 + 7)

T = int(input().strip())


# N, M = map(int, input().split())

def find(a, par):
    if par[a] != a:
        par[a] = find(par[a], par)
    return par[a]


def union(a, b, par):
    x = find(a, par)
    y = find(b, par)
    if x != y:
        if x < y:
            par[x] = y
        elif x > y:
            par[y] = x
        return 1
    return 0


for _ in range(T):
    N, m1, m2 = map(int, input().split())
    g1 = []
    g2 = []
    p1 = [i for i in range(N + 5)]
    p2 = [i for i in range(N + 5)]

    for _ in range(m1):
        u, v = map(int, input().split())
        g1.append((u, v))

    for _ in range(m2):
        u, v = map(int, input().split())
        g2.append((u, v))

    for u, v in g2:
        union(u, v, p2)
    for i in range(1, N+1):
        find(i, p2)
    res = 0
    for u, v in g1:
        x, y = find(u, p1), find(v, p1)
        if find(p2[x], p2) != find(p2[y], p2):
            res += 1
        else:
            union(x, y, p1)
    for i in range(1, N + 1):
        if find(i, p1) != find(i, p2):
            res += 1
            union(find(i, p2), find(i, p1), p1)
    print(res)

C++

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

// Union-Find의 find 함수
int find(int a, vector<int>& parent) {
    if (parent[a] != a) {
        parent[a] = find(parent[a], parent); // 경로 압축
    }
    return parent[a];
}

// Union-Find의 union 함수
bool unionSets(int a, int b, vector<int>& parent) {
    int x = find(a, parent);
    int y = find(b, parent);
    if (x != y) {
        if (x < y) {
            parent[x] = y;
        } else {
            parent[y] = x;
        }
        return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int N, m1, m2;
        cin >> N >> m1 >> m2;

        vector<pair<int, int>> g1, g2;
        vector<int> p1(N + 5), p2(N + 5);

        // 부모 배열 초기화
        for (int i = 0; i <= N + 4; i++) {
            p1[i] = i;
            p2[i] = i;
        }

        // g1 간선 입력
        for (int i = 0; i < m1; i++) {
            int u, v;
            cin >> u >> v;
            g1.emplace_back(u, v);
        }

        // g2 간선 입력
        for (int i = 0; i < m2; i++) {
            int u, v;
            cin >> u >> v;
            g2.emplace_back(u, v);
        }

        // g2의 간선으로 p2 연결
        for (const auto& edge : g2) {
            int u = edge.first;
            int v = edge.second;
            unionSets(u, v, p2);
        }

        // 모든 노드의 최상위 부모 찾기 (p2 경로 압축)
        for (int i = 1; i <= N; i++) {
            find(i, p2);
        }

        int res = 0;

        // g1의 간선 처리
        for (const auto& edge : g1) {
            int u = edge.first;
            int v = edge.second;
            int x = find(u, p1);
            int y = find(v, p1);
            if (find(p2[x], p2) != find(p2[y], p2)) {
                res++;
            } else {
                unionSets(x, y, p1);
            }
        }

        // p1과 p2를 비교하여 최종 연결
        for (int i = 1; i <= N; i++) {
            if (find(i, p1) != find(i, p2)) {
                res++;
                unionSets(find(i, p2), find(i, p1), p1);
            }
        }

        cout << res << '\n';
    }

    return 0;
}