Submission #1235646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235646		gry3125	Drivers (BOI24_drivers)	C++20	100 / 100	250 ms	25536 KiB

Main

#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
using namespace std;

ll par[200005], sz[200005];
ll find(ll a) {
    if (par[a] == a) return a;
    return par[a] = find(par[a]);
}
void merge(ll a, ll b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a; sz[a] += sz[b]; sz[b] = 0;
}

int main() {
    int n, m, u; cin >> n >> m >> u;
    for (ll i = 1; i <= n; i++) {
        par[i] = i; sz[i] = 1;
    }
    vector<pair<ll,pair<ll,ll>>> e;
    for (int i = 0; i < m; i++) {
        ll a, b, t; cin >> a >> b >> t;
        e.pb({t, {a, b}});
    }
    vector<pair<pair<ll,ll>,pair<ll,ll>>> q;
    for (int i = 0; i < u; i++) {
        ll a, b, p; cin >> a >> b >> p;
        q.pb({{p, i}, {a, b}});
    }
    sort(all(e)); sort(all(q));
    vector<string> ans(u);
    int cur = 0; // havent merge
    for (int i = 0; i < u; i++) {
        ll a = q[i].se.fi, b = q[i].se.se;
        ll p = q[i].fi.fi, id = q[i].fi.se;
        while (cur < m && e[cur].fi <= p) {
            merge(e[cur].se.fi, e[cur].se.se); cur++;
        }
        a = find(a); b = find(b);
        if (a == b) ans[id] = "TAIP";
        else ans[id] = "NE";
    }
    for (int i = 0; i < u; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

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