Submission #1153160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153160		tvgk	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2096 ms	5448 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 1e5 + 7, nB = 275;

int dp[mxN], n, m, q;
bool dd[mxN];
vector<int> w[mxN];
vector<ii> ans[mxN];

int Topo(int j)
{
    for (int i = 1; i <= j; j++)
        dp[i] = -1;

    for (int i = 1; i <= j; i++)
    {
        if (dd[i])
            continue;

        dp[i] = max(0, dp[i]);
        for (int u : w[i])
            dp[u] = max(dp[u], dp[i] + 1);
    }

    return dp[j];
}

vector<ii> Merge(vector<ii>& u, vector<ii>& v)
{
    vector<ii> res, tmp;
    vector<int> mem;

    merge(u.begin(), u.end(), v.begin(), v.end(), back_inserter(tmp));
    for (ii i : tmp)
    {
        if (res.size() > nB)
            break;

        if (dd[i.se])
            continue;
        dd[i.se] = 1;

        mem.push_back(i.se);
        res.push_back(i);
    }

    for (int i : mem)
        dd[i] = 0;

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        w[u].push_back(v);
    }

    for (int i = 1; i <= n; i++)
    {
        for (ii& j : ans[i])
            j.fi--;
        ans[i].push_back({0, i});

        for (int j : w[i])
            ans[j] = Merge(ans[i], ans[j]);
    }

    for (int i = 1; i <= q; i++)
    {
        int vt, num;
        cin >> vt >> num;

        vector<int> mem(num);
        for (int& j : mem)
        {
            cin >> j;
            dd[j] = 1;
        }

        int res = -1;
        if (num < nB)
        {
            for (ii j : ans[vt])
            {
                if (!dd[j.se])
                {
                    res = -j.fi;
                    break;
                }
            }
        }
        else
            res = Topo(vt);
        cout << res << '\n';

        for (int j : mem)
            dd[j] = 0;
    }
}

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