제출 #1177637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177637		Zicrus	Drivers (BOI24_drivers)	C++20	55 / 100	2039 ms	854720 KiB

Main

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

typedef long long ll;

struct entry {
    ll lnk, rank;
};

struct tree {
    entry val;
    ll sz;
    tree *left, *right;
};

tree *update(tree *tr, ll lo, ll hi, ll i, entry v) {
    tr = tr ? new tree(*tr) : new tree();
    ll mid = (lo + hi) / 2;
    if (i == mid) tr->val = v;
    else if (i <= mid) tr->left = update(tr->left, lo, mid, i, v);
    else tr->right = update(tr->right, mid+1, hi, i, v);
    return tr;
}

entry get(tree *tr, ll lo, ll hi, ll i) {
    ll mid = (lo + hi) / 2;
    if (i == mid) return tr->val;
    else if (i <= mid) return get(tr->left, lo, mid, i);
    else return get(tr->right, mid+1, hi, i);
}

ll n;
vector<tree*> trees;

entry find(ll t, ll a) {
    entry v = get(trees[t], 0, n-1, a);
    if (v.lnk != a) trees[t] = update(trees[t], 0, n-1, a, v = find(t, v.lnk));
    return v;
}

tree *unite(ll t, ll a, ll b) {
    entry x = find(t, a), y = find(t, b);
    if (x.lnk == y.lnk) return trees[t];
    if (x.rank < y.rank) swap(x, y);
    tree* nw = update(trees[t], 0, n-1, y.lnk, x);
    if (x.rank == y.rank) nw = update(nw, 0, n-1, x.lnk, {x.lnk, x.rank + 1});
    return nw;
}

int main() {
    ll m, q; cin >> n >> m >> q;
    priority_queue<pair<ll, pair<ll, ll>>> pq;
    while (m--) {
        ll x, y, t; cin >> x >> y >> t; x--; y--;
        pq.push({-t, {x, y}});
    }

    trees = vector<tree*>(1);
    for (int i = 0; i < n; i++) {
        trees[0] = update(trees[0], 0, n-1, i, {i, 0});
    }

    vector<ll> ts;
    while (!pq.empty()) {
        ts.push_back(-pq.top().first);
        pair<ll, ll> cur = pq.top().second; pq.pop();
        trees.push_back(unite(trees.size()-1, cur.first, cur.second));
    }

    while (q--) {
        ll a, b, p; cin >> a >> b >> p; a--; b--;
        ll id = upper_bound(ts.begin(), ts.end(), p) - ts.begin();
        if (id == 0) {
            cout << "NE\n";
            continue;
        }
        if (find(id, a).lnk == find(id, b).lnk) cout << "TAIP\n";
        else cout << "NE\n";
    }
}

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