Submission #670804

#	Time	Username	Problem	Language	Result	Execution time	Memory
670804		chuangsheep	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	2089 ms	944 KiB

bitaro

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

using pi = pair<int, int>;

int BLOCK;

void build_dist_arr(int node,
                    const vector<vector<int>> &adj,
                    vector<set<pi, greater<pi>>> &anc,
                    vector<unordered_map<int, int>> &act)
{
    anc[node].insert({0, node});
    for (auto &child : adj[node])
    {
        for (auto &[dist, from_node] : anc[node])
        {
            if (act[child][from_node] == 0)
            {
                anc[child].insert({dist + 1, from_node});
                act[child][from_node] = dist + 1;
            }
            else
            {
                if (act[child][from_node] < dist + 1)
                {
                    anc[child].erase({act[child][from_node], from_node});
                    anc[child].insert({dist + 1, from_node});
                    act[child][from_node] = dist + 1;
                }
            }
            if (anc[child].size() > BLOCK)
            {
                act[child][(*anc[child].rbegin()).second] = 0;
                anc[child].erase(prev(anc[child].end()));
            }
        }
    }
    for (auto &child : adj[node])
    {
        build_dist_arr(child, adj, anc, act);
    }
}

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<set<pi, greater<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;
    BLOCK = (int)sqrt(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<set<pi, greater<pi>>> ancestors(N);
    vector<unordered_map<int, int>> anc_ct(N);
    build_dist_arr(0, adj, ancestors, anc_ct);

    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::set<std::pair<int, int>, std::greater<std::pair<int, int> > > >&, std::vector<std::unordered_map<int, int> >&)':
bitaro.cpp:32:35: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int>, std::greater<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |             if (anc[child].size() > BLOCK)
      |                 ~~~~~~~~~~~~~~~~~~^~~~~~~

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