Submission #1111358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111358		gelastropod	Drivers (BOI24_drivers)	C++14	100 / 100	360 ms	33204 KiB

Main

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

typedef pair<int, pair<int, int>> iii;
typedef pair<int, pair<pair<int, int>, int>> iiii;
typedef pair<int, string> ii;

vector<int> p;

int fin(int a)
{
    if (p[a] == a)
        return a;
    return p[a] = fin(p[a]);
}

void join(int a, int b)
{
    a = fin(a);
    b = fin(b);
    if (a == b) return;
    p[a] = b;
}

signed main()
{
    int N, M, U, x, y, t;
    cin >> N >> M >> U;
    for (int i = 0; i < N; i++)
        p.push_back(i);
    priority_queue<iii, vector<iii>, greater<iii>> pq;
    priority_queue<iiii, vector<iiii>, greater<iiii>> query;
    for (int i = 0; i < M; i++)
    {
        cin >> x >> y >> t;
        x--, y--;
        pq.push({t, {x, y}});
    }
    for (int i = 0; i < U; i++)
    {
        cin >> x >> y >> t;
        x--, y--;
        query.push({t, {{x, y}, i}});
    }
    priority_queue<ii, vector<ii>, greater<ii>> ans;
    while (!query.empty())
    {
        auto i = query.top();
        query.pop();
        while (!pq.empty() && pq.top().first <= i.first)
        {
            auto j = pq.top();
            pq.pop();
            join(j.second.first, j.second.second);
        }
        if (fin(i.second.first.first) == fin(i.second.first.second))
            ans.push({i.second.second, "TAIP\n"});
        else
            ans.push({i.second.second, "NE\n"});
    }
    while (!ans.empty())
    {
        cout << ans.top().second;
        ans.pop();
    }
}

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