Submission #670821

#	Time	Username	Problem	Language	Result	Execution time	Memory
670821		chuangsheep	Bitaro’s Party (JOI18_bitaro)	C++11	14 / 100	2035 ms	291856 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>> &radj,
                    vector<vector<pi>> &anc)
{
    for (int i = 0; i < N; i++)
    {
        vector<int> dists(N, -1);
        vector<int> from;
        for (auto &parent : radj[i])
        {
            for (auto &[d, f] : anc[parent])
            {
                if (f == -1)
                    break;
                if (dists[f] == -1)
                {
                    dists[f] = d + 1;
                    from.push_back(f);
                }
                else
                {
                    if (dists[f] < d + 1)
                    {
                        dists[f] = d + 1;
                    }
                }
            }
        }

        from.push_back(i);
        dists[i] = 0;
        sort(from.begin(), from.end(), [&](int a, int b)
             { return dists[a] > dists[b]; });

        for (int j = 0; j < BLOCK && j < from.size(); j++)
        {
            anc[i][j] = {dists[from[j]], from[j]};
        }
    }
}

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

    vector<vector<pi>> ancestors(N, vector<pi>(BLOCK, {-1, -1}));
    build_dist_arr(N, radj, ancestors);

    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;
}

Compilation message (stderr)

bitaro.cpp: In function 'void build_dist_arr(int, const std::vector<std::vector<int> >&, std::vector<std::vector<std::pair<int, int> > >&)':
bitaro.cpp:18:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |             for (auto &[d, f] : anc[parent])
      |                        ^
bitaro.cpp:42:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int j = 0; j < BLOCK && j < from.size(); j++)
      |                                      ~~^~~~~~~~~~~~~
bitaro.cpp: In function 'int scan(int, const std::vector<std::vector<std::pair<int, int> > >&, const std::unordered_set<int>&)':
bitaro.cpp:72:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for (auto &[dist, from] : anc[node])
      |                ^

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