Submission #670844

#	Time	Username	Problem	Language	Result	Execution time	Memory
670844		chuangsheep	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1330 ms	288960 KiB

bitaro

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

using pi = pair<int, int>;

const int BLOCK = 350;

void build_dist_arr(int N,
                    const vector<vector<int>> &adj,
                    vector<vector<pi>> &anc,
                    vector<int> &size)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < size[i]; j++)
        {
            anc[i][j].first++;
        }

        for (auto &child : adj[i])
        {
            int entries = size[i] + size[child];
            vector<pi> temp;
            temp.reserve(entries + 3);
            merge(anc[i].begin(), anc[i].begin() + size[i],
                  anc[child].begin(), anc[child].begin() + size[child],
                  back_inserter(temp), greater<pi>());
            vector<bool> used(N, false);
            size[child] = 0;
            for (int j = 0; j < entries; j++)
            {
                if (used[temp[j].second])
                    continue;
                anc[child][size[child]++] = temp[j];
                used[temp[j].second] = true;
                if (size[child] == BLOCK)
                    break;
            }
        }
    }
}

int search(int node, const vector<vector<int>> &adj, const unordered_set<int> &busy)
{
    vector<int> mx(node + 1, 0);
    for (int i = 0; i < node; i++)
    {
        for (auto &child : adj[i])
        {
            if (child > node)
                continue;
            if (busy.count(i) == 0 || mx[i] > 0)
                mx[child] = max(mx[child], mx[i] + 1);
        }
    }
    if (mx[node] == 0)
    {
        if (busy.count(node))
            return -1;
    }
    return mx[node];
}

int scan(int node, const vector<vector<pi>> &anc, const unordered_set<int> &busy)
{
    for (auto &[dist, from] : anc[node])
    {
        if (busy.count(from))
            continue;
        return dist;
    }
    return -1;
}

int main()
{
#if defined(DEBUG)
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    cin.tie(0)->sync_with_stdio(false);
#endif

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
    }

    vector<vector<pi>> ancestors(N, vector<pi>(BLOCK, {-1, -1}));
    for (int i = 0; i < N; i++)
    {
        ancestors[i][0] = {-1, i};
    }
    vector<int> size(N, 1);
    build_dist_arr(N, adj, ancestors, size);

    for (int q = 0; q < Q; q++)
    {
        int T, Y;
        cin >> T >> Y;
        T--;
        unordered_set<int> busy;
        for (int _ = 0; _ < Y; _++)
        {
            int y;
            cin >> y;
            y--;
            busy.insert(y);
        }

        if (Y >= BLOCK)
        {
            cout << search(T, adj, busy) << "\n";
        }
        else
        {
            cout << scan(T, ancestors, busy) << "\n";
        }
    }
    cout << flush;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86