Submission #1179765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179765		repsak	Drivers (BOI24_drivers)	C++20	0 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<ll> back;
vector<ll> length;
vector<vector<ll>> costAdj;


ll findParent(ll b){
    while(back[b] != b){
        b = back[b];
    }

    return b;
}

bool possible(ll a, ll b){
    return findParent(a) == findParent(b);
}

void merge(ll a, ll b){
    ll pA = findParent(a);
    ll pB = findParent(b);
    if(pA == pB) return;

    if(length[pA] < length[pB]) swap(pA, pB);

    back[b] = a;
    length[a] += b;
}

int main(){
    ll N, M, Q;
    cin >> N >> M >> Q;

    back.resize(N + 1);
    length.resize(N + 1);

    for(ll i = 1; i <= N; i++){
        back[i] = i;
        length[i] = 1;
    }

    for(ll i = 0; i < M; i++){
        ll a, b, c;
        cin >> a >> b >> c;

        costAdj.push_back({c, a, b});
    }

    sort(costAdj.begin(), costAdj.end());

    vector<vector<ll>> queries(Q);
    for(ll i = 0; i < Q; i++){
        ll a, b, c;
        cin >> a >> b >> c;

        queries[i] = {c, a, b, i};
    }

    sort(queries.begin(), queries.end());

    // 1) Minimum spanning tree
    vector<ll> order(Q);
    ll iQ = 0;

    for(ll i = 0; i < costAdj.size(); i++){
        if(iQ < queries.size() && queries[iQ][0] == costAdj[i][0]){
            merge(costAdj[i][1], costAdj[i][2]);
        }

        while(iQ < queries.size() && queries[iQ][0] <= costAdj[i][0]){
            if(possible(queries[iQ][1], queries[iQ][2])){
                order[queries[iQ][3]] = 1;
            }
            iQ++;
        }

        merge(costAdj[i][1], costAdj[i][2]);
    }

    for(ll i = 0; i < Q; i++){
        if(order[i]) cout << "TAIP\n";
        else cout << "NE\n";
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 23
• Subtask 5: 0 / 45