Submission #1159929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159929		pointsix	Drivers (BOI24_drivers)	C++20	0 / 100	2 ms	2632 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<array<long long, 3>> val3;
typedef vector<array<long long, 4>> val4;
typedef vector<long long> vl;

ll p[300000];
ll sz[300000];

ll find(ll a){
    return p[a] == a ? a : p[a] = find(p[a]);
}

void unite(ll a, ll b){
    ll at = find(a); ll bt = find(b);
    if(at == bt) return;
    if(sz[bt] > sz[at]) swap(at, bt);
    p[bt] = at; sz[at] += sz[bt];
}

int main(){
    ll n, m, q; cin >> n >> m >> q;
    val3 roads = val3 (m);
    for(int i = 0; i < 300000; i++) p[i] = i;
    for(int i = 0; i < m; i++){
        cin >> roads[i][1] >> roads[i][2] >> roads[i][0];
        roads[i][1]--; roads[i][2]--;
    }
    sort(roads.begin(), roads.end());
    val4 qrs = val4 (q);
    for(int i = 0; i < q; i++){
        cin >> qrs[i][1] >> qrs[i][2] >> qrs[i][0];
        qrs[i][1]--; qrs[i][2]--;
        qrs[i][3] = i;
    }
    sort(qrs.begin(), qrs.end());
    vl ans = vl (q);
    int pnt = 0;
    for(auto i : qrs){
        while(pnt < m && roads[pnt][0] < i[0]){
            unite(roads[pnt][1], roads[pnt][2]);
            pnt++;
        }
        ans[i[3]] = find(i[1]) == find(i[2]);
    }
    for(auto i : ans){
        cout << (i ? "TAIP" : "NE") << '\n';
    }
}

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