Submission #433731

#	Time	Username	Problem	Language	Result	Execution time	Memory
433731		someone	Bridges (APIO19_bridges)	C++14	14 / 100	112 ms	10152 KiB

bridges

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

struct Event {
    bool isQ;
    int w, deb, fin, pos, id;
};

const int N = 1e5 + 42;

vector<Event> event;
int n, m, q, par[N], sz[N], ans[N];

int F(int i) {
    if(par[i] == i)
        return i;
    return par[i] = F(par[i]);
}

void U(int a, int b) {
    a = F(a), b = F(b);
    if(a == b)
        return;
    if(sz[a] < sz[b])
        swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int e1, e2, w;
        cin >> e1 >> e2 >> w;
        e1--, e2--;
        event.push_back({false, w, e1, e2, -1, -1});
    }
    cin >> q;
    for(int i = 0; i < q; i++) {
        int type, id, w;
        cin >> type >> id >> w;
        id--;
        event.push_back({true, w, -1, -1, id, i});
    }

    for(int i = 0; i < n; i++) {
        sz[i] = 1;
        par[i] = i;
    }

    sort(event.begin(), event.end(),
    [](Event a, Event b) {
        if(a.w == b.w) {
            if(a.isQ)
                return false;
            return b.isQ;
        }
        return a.w > b.w;
    });

    for(Event e : event) {
        if(e.isQ) {
            ans[e.id] = sz[F(e.pos)];
        } else {
            U(e.deb, e.fin);
        }
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

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