Submission #1159970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159970		12345678	Drivers (BOI24_drivers)	C++20	100 / 100	134 ms	10384 KiB

Main

#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");
}

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