Submission #372524

#	Time	Username	Problem	Language	Result	Execution time	Memory
372524		gustason	Trucks (LMIO17_sunkvezimiai)	C++11	100 / 100	172 ms	15212 KiB

sunkvezimiai

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 2e5 + 5;
int parent[maxN], sz[maxN], mx[maxN];
struct Edge {
    int a, b, w;
    bool operator<(Edge other) const {
        return w < other.w;
    }
};
struct Query {
    int a, b, t, idx;
    bool operator<(Query other) const {
        return t < other.t;
    }
};
int find(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find(parent[v]);
}
void unite(int a, int b) {
    a = find(a), b = find(b);

    if (a == b) return;
    if (sz[a] < sz[b]) {
        swap(a, b);
    }
    parent[b] = a;
    sz[a] += sz[b];
}
bool can(int a, int b) {
    return find(a) == find(b);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i <= n; i++) {
        sz[i] = 1;
        parent[i] = i;
    }

    vector<Edge> e(m);
    for(int i = 0; i < m; i++) {
        cin >> e[i].a >> e[i].b >> e[i].w;
    }
    vector<Query> qs(q);
    for(int i = 0; i < q; i++) {
        cin >> qs[i].a >> qs[i].b >> qs[i].t;
        qs[i].idx = i;
    }
    sort(qs.begin(), qs.end());
    sort(e.begin(), e.end());

    vector<bool> res(q);
    int idx = 0;
    for(int i = 0; i < q; i++) {
        while(idx < m && e[idx].w <= qs[i].t) {
            unite(e[idx].a, e[idx].b);
            idx++;
        }
        res[qs[i].idx] = can(qs[i].a, qs[i].b);
    }
    for(bool i : res) {
        if (i)
            cout << "TAIP\n";
        else
            cout << "NE\n";
    }
    return 0;
}

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