Submission #1181466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181466		repsak	Drivers (BOI24_drivers)	C++20	100 / 100	251 ms	23152 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[pB] = pA;
    length[pA] += length[pB];
}

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});
    }

    
    vector<tuple<ll, ll, ll, 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(costAdj.begin(), costAdj.end());
    sort(queries.begin(), queries.end());

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

    // for(ll i = 0; i < costAdj.size(); i++){
    for(auto [c, a, b, idx] : queries){

        while(iR < M && costAdj[iR][0] <= c){
            merge(costAdj[iR][1], costAdj[iR][2]);
            iR++;
        }

        if(possible(a, b)) order[idx] = 1;
    }

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

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