Submission #1235629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235629		gry3125	Drivers (BOI24_drivers)	C++20	21 / 100	216 ms	5436 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;

vector<ll> hist[55];

ll par[500005], sz[500005];
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}});
    }
    sort(all(e));
    for (int t = 1; t <= 50; t++) {
        for (int i = 0; i < m; i++) {
            if (e[i].fi <= t) {
                merge(e[i].se.fi, e[i].se.se);
            }
        }
        hist[t].resize(n+1);
        for (int i = 1; i <= n; i++) {
            hist[t][i] = find(i);
        }
    }
    while (u--) {
        ll a, b, p; cin >> a >> b >> p;
        if (p > 50) p = 50;
        a = hist[p][a]; b = hist[p][b];
        cout << (a == b ? "TAIP" : "NE") << "\n";
    }
    return 0;
}

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