Submission #1339955

#TimeUsernameProblemLanguageResultExecution timeMemory
1339955ZicrusDrivers (BOI24_drivers)C++20
100 / 100
115 ms16776 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
constexpr ll inf = 4e18;
mt19937 mt(time(0));

struct union_find {
    vector<ll> p, s;

    union_find(ll n) : p(n), s(n, 1) {
        iota(all(p), 0ll);
    }

    ll find(ll a) {
        if (p[a] != a) p[a] = find(p[a]);
        return p[a];
    }

    bool merge(ll a, ll b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (s[a] < s[b]) swap(a, b);
        p[b] = a;
        s[a] += b;
        return true;
    }
};

void solve() {
    ll n, m, q; cin >> n >> m >> q;
    vector<pair<ll, pll>> edges(m);
    for (auto &[w, e] : edges) cin >> e.first >> e.second >> w, e.first--, e.second--;
    sort(all(edges));
    vector<array<ll, 4>> qs(q); // {u, a, b, qid}
    for (ll i = 0; i < q; i++) {
        cin >> qs[i][1] >> qs[i][2] >> qs[i][0];
        qs[i][1]--; qs[i][2]--;
        qs[i][3] = i;
    }
    sort(all(qs));
    union_find dsu(n);
    vector<ll> res(q);
    ll p = 0;
    for (auto &[u, a, b, qid] : qs) {
        while (p < m && edges[p].first <= u) {
            dsu.merge(edges[p].second.first, edges[p].second.second);
            p++;
        }
        res[qid] = (dsu.find(a) == dsu.find(b));
    }
    for (auto &e : res) cout << (e ? "TAIP\n" : "NE\n");
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...