Submission #1279629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279629		raphaelp	Drivers (BOI24_drivers)	C++20	0 / 100	4 ms	2316 KiB

Main

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

struct UnionFind
{
    vector<int> p;
    UnionFind(int x)
    {
        p.assign(x, 0);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) { return (x == p[x]) ? x : p[x] = find(p[x]); }
    int merge(int a, int b)
    {
        int x = find(a), y = find(b);
        if (x == y)
            return 0;
        p[x] = y;
        return 1;
    }
};

void dfs(int x, int p, vector<vector<pair<int, int>>> &AR, vector<vector<int>> &lca, vector<vector<int>> &lca2, vector<int> &depth, int prof)
{
    depth[x] = prof;
    lca[0][x] = p;
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i].first == p)
            continue;
        lca2[0][AR[x][i].first] = AR[x][i].second;
        dfs(AR[x][i].first, x, AR, lca, lca2, depth, prof + 1);
    }
}

int main()
{
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<vector<int>> AR2;
    vector<vector<pair<int, int>>> AR(N);
    for (int i = 0; i < M; i++)
    {
        int a, b, t;
        cin >> a >> b >> t;
        a--, b--;
        AR2.push_back({t, a, b});
    }
    for (int i = 0; i < N - 1; i++)
    {
        AR2.push_back({1000000001, i, i + 1});
    }
    sort(AR2.begin(), AR2.end());
    UnionFind UF(N);
    for (int i = 0; i < AR2.size(); i++)
    {
        if (UF.merge(AR2[i][1], AR2[i][2]))
        {
            AR[AR2[i][1]].push_back({AR2[i][2], AR2[i][0]});
            AR[AR2[i][2]].push_back({AR2[i][1], AR2[i][0]});
        }
    }
    vector<vector<int>> lca(log2(N) + 1, vector<int>(N)), lca2(log2(N) + 1, vector<int>(N));
    vector<int> depth(N);
    dfs(0, 0, AR, lca, lca2, depth, 0);
    for (int i = 1; i <= log2(N); i++)
    {
        for (int j = 0; j < N; j++)
        {
            lca[i][j] = lca[i - 1][lca[i - 1][j]];
            lca2[i][j] = max(lca2[i - 1][j], lca2[i - 1][lca[i - 1][j]]);
        }
    }
    for (int i = 0; i < Q; i++)
    {
        int a, b, t;
        cin >> a >> b >> t;
        a--, b--;
        int maxx = 0;
        if (depth[a] > depth[b])
            swap(a, b);
        for (int j = log2(N); j >= 0; j--)
        {
            if (depth[lca[j][b]] >= depth[a])
            {
                maxx = max(maxx, lca2[j][b]);
                b = lca[j][b];
            }
        }
        if (a != b)
        {
            for (int j = log2(N); j >= 0; j--)
            {
                if (lca[j][a] != lca[j][b])
                {
                    maxx = max(maxx, max(lca2[j][a], lca2[j][b]));
                    b = lca2[j][b];
                    a = lca2[j][a];
                }
            }
            maxx = max(maxx, max(lca2[0][a], lca2[0][b]));
        }
        if (maxx > t)
            cout << "NE" << '\n';
        else
            cout << "TAIP" << '\n';
    }
}

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