Submission #1229364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229364		marsasgrg	다리 (APIO19_bridges)	C++20	0 / 100	121 ms	4532 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
    vector<int> P;
    vector<int> S;
    UnionFind(int N) {
        P.resize(N);
        S.resize(N);

        for (int i = 0; i < N; i++) {
            P[i] = i;
            S[i] = 1;
        }
    }
    int raskSakni(int x) {
        if (P[x] == x) {
            // Jau radome.
            return x;
        }

        // Ieškome šaknies rekursyviai
        int saknis = raskSakni(P[x]);
        // Atnaujiname tėvą, kad kitą kartą rastume greičiau
        P[x] = saknis;
        return saknis;
    }
    int aibesDydis(int x) {
        // Tik šakniniai elementai saugo tikrą aibės dydį!
        return S[raskSakni(x)];
    }
    bool sujungti(int x, int y) {
        x = raskSakni(x);
        y = raskSakni(y);

        if (x == y) {
            // Jau vienoje aibėje.
            return false;
        }

        if (S[x] > S[y]) {
            swap(x, y);
            // `x` dydis mažesnis arba lygus `y` dydžiui.
        }

        P[x] = y;  // Pakeičiame x tėvą į y.
        S[y] += S[x]; // Atnaujiname y dydį. S[x] tampa nesvarbus, nes x nebėra šakninis elementas.
        return true;
    }
    bool arVienojeAibeje(int x, int y) {
        return raskSakni(x) == raskSakni(y);
    }
};


int main() {
    // node i yra bridge tarp i, i+1
    int n, m, q;
    cin >> n >> m;
    UnionFind union_find(n);
    vector<pair<int, pair<int, int>>> tiltai;
    for (int i = 0; i < m; i++) {
        int ui, vi, di;
        cin >> ui >> vi >> di;
        tiltai.push_back({di, {ui - 1, vi - 1}});
    }
    sort(tiltai.begin(), tiltai.end());
    vector<pair<int, pair<int, int>>> queries;

    cin >> q;
    vector<int> ans(q);
    for (int i = 0; i < q; i++){
        int t;
        cin >> t;

        if (t == 1) {
            throw;
        }
        int s, w;
        cin >> s >> w;
        s--;
        queries.push_back({w, {s, i}});
    }
    sort(queries.begin(), queries.end());
    int lastAddedInd = -1;
    for (auto [carWeight, places]: queries) {
        while (true) {
            if (lastAddedInd == m - 1) break;
            if (auto [bridgeWeight, islands] = tiltai[min(m, lastAddedInd + 1)]; bridgeWeight <= carWeight) {
                lastAddedInd++;
                union_find.sujungti(islands.first, islands.second);
            }
            else break;
        }
        ans[places.second] = union_find.aibesDydis(places.first);

    }
    for (const auto i: ans) cout << i << "\n";
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27