Submission #1159970

#TimeUsernameProblemLanguageResultExecution timeMemory
115997012345678Drivers (BOI24_drivers)C++20
100 / 100
134 ms10384 KiB
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, m, q, u, v, w, dsu[nx], res[nx], idx, a[nx], b[nx];
vector<tuple<int, int, int>> edg;
vector<pair<int, int>> qrs;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<=n; i++) dsu[i]=i;
    for (int i=1; i<=m; i++) cin>>u>>v>>w, edg.push_back({w, u, v});
    sort(edg.begin(), edg.end());
    for (int i=1; i<=q; i++) cin>>a[i]>>b[i]>>w, qrs.push_back({w, i});
    sort(qrs.begin(), qrs.end());
    for (int i=0; i<q; i++)
    {
        while (idx<m)
        {
            auto [w, u, v]=edg[idx];
            if (w>qrs[i].first) break;
            dsu[find(u)]=find(v);
            idx++;
        }
        if (find(a[qrs[i].second])==find(b[qrs[i].second])) res[qrs[i].second]=1;
    }
    for (int i=1; i<=q; i++) cout<<(res[i]?"TAIP\n":"NE\n");
}
#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...