Submission #1275402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275402		ngocphu	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2090 ms	412308 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxN = 1e5 + 4;
int n, m, q, s = 100, a[maxN];
vector<int> E[maxN];
bool block[maxN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    // freopen(".INP","r",stdin);
    // freopen(".OUT","w",stdout);

    cin >> n >> m >> q;

    s = sqrt(n);

    for (int i = 1; i <= m; ++i)
    {
        int u, v; cin >> u >> v;

        E[u].push_back(v);
        E[v].push_back(u);
    }

    vector<vector<pair<int,int>>> path_size(n + 1);
    vector<int> from(n + 1, -1);

    // preprocessing

    for (int u = 1; u <= n; ++u)
    {
        path_size[u].push_back({0, u});
        vector<int> from_idx;

        for (int v : E[u])
        {
            for (pair<int,int> x : path_size[v])
            {
                int dist = x.first;
                int idx = x.second;

                if (from[idx] == -1)
                {
                    from_idx.push_back(idx);
                    from[idx] = dist + 1;
                }
                else from[idx] = max(from[idx], dist + 1);
            }
        }

        for (int v : from_idx) path_size[u].push_back({from[v], v});

        sort(path_size[u].rbegin(), path_size[u].rend());

        while(path_size[u].size() > s) path_size[u].pop_back();

        for (int v : from_idx) from[v] = -1;
    }

    // end preprocessing

    for (int i = 1; i <= q; ++i)
    {
        int t, y; cin >> t >> y;

        for (int j = 1; j <= y; ++j)
        {
            cin >> a[j];
            block[a[j]] = true;
        }

        int ans = -1;

        if (y >= s)
        {
            vector<int> dp(n + 1, -1);
            dp[t] = 0;

            for (int u = t; u >= 1; --u)
            {
                if (dp[u] == -1) continue;
                if (!block[u]) ans = max(ans, dp[u]);
                for (int v : E[u]) dp[v] = max(dp[v], dp[u] + 1);
            }
        }
        else
        {
            for (pair<int,int> x : path_size[t])
            {
                int dist = x.first;
                int idx = x.second;

                if (!block[idx])
                {
                    ans = max(ans, dist);
                    break;
                }
            }
        }

        cout << ans << "\n";

        for (int j = 1; j <= y; ++j) block[a[j]] = false;
    }

    return 0;
}

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