部屋をきれいにする

13342 ワード
Union Find ps python cpp DisjointSet テキストリンク

部屋を掃除する


部屋をきれいにする

アイデア


引き出し間でunion演算を実行します.このとき,ルートは接続された引き出しに何個の空きがあるかを負の数で表す.
このように瓶を入力するたびに、この酒が保存できるか、飲むべきかがわかります.
保存できる場合は(入力した2つの引き出しのルートを参照し、残りの場所があることを確認してください)、2つの引き出しを結合し、ルートに1つの位置が埋め込まれていることをマークします.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

int N, L;
int p[300001];

int find(int n) {
    if (p[n] <= 0) return n;
    return p[n] = find(p[n]);
}

void Union(int n1, int n2) {
    n1 = find(n1);
    n2 = find(n2);
    if (n1 == n2) return;
    else {
        p[n1] += p[n2];
        p[n2] = n1;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> L;

    memset(p, -1, sizeof(p));

    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        if (-p[find(a)] - p[find(b)] > 0) {
            cout << "LADICA\n";
            Union(a, b);
            p[find(a)]++;
        }
        else {
            cout << "SMECE\n";
        }
    }

    return 0;
}
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

p = [-1]*300001

def find(n):
    if p[n] <= 0:
        return n
    p[n] = find(p[n])
    return p[n]

def union(n1, n2):
    n1 = find(n1)
    n2 = find(n2)
    if n1 == n2:
        return
    p[n1] += p[n2]
    p[n2] = n1

N, L = map(int, input().split())

for _ in range(N):
    a, b = map(int, input().split())
    if p[find(a)] + p[find(b)] < 0:
        print("LADICA")
        union(a, b)
        p[find(a)] += 1
    else:
        print("SMECE")

おしゃべり


配列pが1つ足りないだけで間違っていることを知っていますが、なぜメモリオーバーフローが表示されているのか分かりません.念のため、Pythonで同じ結果を解いたIndexErrorが発見しました.1つのグリッドを参照して再帰関数を呼び出し続け、スタックが爆発したと推定します.
そしてこの問題の時間は私が3位です.
Python Numpy基本構文
テンセントaiプラットフォームをカプセル化して身分証明書を識別するのは静的な方法です