Submission #1159895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159895		ach00	Drivers (BOI24_drivers)	C++20	100 / 100	245 ms	10360 KiB

Main

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

vector<int> pt;
vector<int> sz;

int find(int u) {
    if(pt[u] != u) pt[u] = find(pt[u]);
    return pt[u]; 
}

void unite(int u, int v) {
    u = find(u);
    v = find(v);
    if(sz[u] > sz[v]) swap(u,v);
    sz[v] += sz[u];
    pt[u] = v;
}


int main() {
    int n,m,q; cin >> n >> m >> q;
    vector<pair<int,pair<int,int>>> edges;
    
    pt.resize(n);
    sz.resize(n,1);
    for(int i = 0; i < n; i++) pt[i] = i;

    for(int i = 0; i < m; i++) {
        int x,y,t; cin >> x >> y >> t;
        x--; y--;
        edges.push_back({t,{x,y}});
    }
    sort(edges.begin(), edges.end());
    vector<pair<pair<int,int>,pair<int,int>>> queries;

    for(int i = 0; i < q; i++) {
        int a,b,p; cin >> a >> b >> p; a--; b--;
        queries.push_back({{p,i},{a,b}});
    }
    sort(queries.begin(), queries.end());
    vector<int> ans(q);
    int least_edge = 0;
    for(int i = 0; i < q; i++) {
        int a,b,p; 
        a = queries[i].second.first;
        b = queries[i].second.second;
        p = queries[i].first.first;
        while(edges[least_edge].first <= p && least_edge < m) {
            unite(edges[least_edge].second.first, edges[least_edge].second.second);
            least_edge++;
        }
        if(find(a) == find(b)) {
            ans[queries[i].first.second] = 1;
        }  else {
            ans[queries[i].first.second] = 0;
        }
    }
    for(int i = 0; i < q; i++) {
        cout << ((ans[i] == 1) ? "TAIP" : "NE") << '\n';
    }
}

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