Submission #1155087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155087		FilipL	Drivers (BOI24_drivers)	C++20	100 / 100	93 ms	8336 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;

#define LOCAL false

const int LIM = 2e5 + 7;
int V, E, q;

struct Edge { int v1, v2, c; };
bool cmp(Edge e1, Edge e2) {
    return e1.c < e2.c;
}

Edge edges[LIM];    // (c, (v1, v2))


pair<int, Edge> queries[LIM];  // (c, idx)
bool qans[LIM];

int par[LIM];
int sz[LIM];
int repr(int v) {
    if (par[v] == v) return v;
    return par[v] = repr(par[v]);
}
void uni(int v1, int v2) {
    v1 = repr(v1);
    v2 = repr(v2);
    if (v1 == v2) return;
    if (sz[v1] < sz[v2]) swap(v1, v2);
    sz[v1] += sz[v2];
    par[v2] = v1;
} 

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (LOCAL) {
        ignore=freopen("io/in", "r", stdin);
        ignore=freopen("io/out", "w", stdout);
    }

    cin >> V >> E >> q;
    int v1, v2, c;
    rep(i, E) {
        cin >> v1 >> v2 >> c;
        edges[i] = {v1, v2, c};
    }
    rep(i, q) {
        cin >> v1 >> v2 >> c;
        queries[i] = {i, {v1, v2, c}};
    }

    sort(edges, edges+E, cmp);
    sort(queries, queries+q, [&](auto q1, auto q2) {
        return cmp(q1.second, q2.second);
    });

    iota(par+1, par+1+V, 1);
    fill(sz+1, sz+1+V, 1);

    int eidx = 0;
    rep(i, q) {
        auto [idx, e] = queries[i];
        while (eidx < E && edges[eidx].c <= e.c) {
            auto [v1, v2, c] = edges[eidx];
            uni(v1, v2);
            eidx++;
        }
        int g1 = repr(e.v1);
        int g2 = repr(e.v2);
        qans[idx] = (g1==g2);
    }

    rep(i, q) cout << (qans[i] ? "TAIP" : "NE") << "\n";

    return 0;
}

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