Submission #1222062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222062		iamhereforfun	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	4 ms	5444 KiB

bitaro

// IamHereForFun //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e5 + 5;
const int Q = 2e5 + 5;
const int M = 32000;
const int C = 26;
const int LG = 20;
const int R = 25e3 + 5;
const int B = 100;
const int O = 3e5 + 5;
const int INF = 1e9 + 5;
const int MOD = 998244353;
const int nx[] = {0, 1, 0, -1}, ny[] = {1, 0, -1, 0};

int n, m, q, vis[N], d[N];
vector<int> adj[N], ptr;
vector<pair<int, int>> longest_path[N];
bool blocked[N];

void solve()
{
    cin >> n >> m >> q;
    for (int x = 0; x < m; x++)
    {
        int a, b;
        cin >> a >> b;
        adj[b].push_back(a);
    }
    memset(vis, -1, sizeof(vis));
    for (int x = 1; x <= n; x++)
    {
        d[x] = -1e9;
        blocked[x] = 0;
        vector<int> v;
        for (int i : adj[x])
        {
            for (auto [dist, idx] : longest_path[i])
            {
                if (vis[idx] == -1)
                {
                    vis[idx] = dist + 1;
                    v.push_back(idx);
                }
                else
                {
                    vis[idx] = max(vis[idx], dist + 1);
                }
            }
        }
        for (int i : v)
            longest_path[x].push_back({vis[i], i});
        longest_path[x].push_back({0, x});
        sort(longest_path[x].rbegin(), longest_path[x].rend());
        while (longest_path[x].size() > B)
            longest_path[x].pop_back();
        for (int i : v)
            vis[i] = -1;
    }
    for (int x = 0; x < q; x++)
    {
        int i, j;
        vector<int> c;
        cin >> i >> j;
        for (int y = 0; y < j; y++)
        {
            int k;
            cin >> k;
            c.push_back(k);
            blocked[k] = 1;
        }
        if (j >= longest_path[x].size())
        {
            d[i] = 0;
            for (int x = i; x > 0; x--)
            {
                for (int k : adj[x])
                {
                    d[k] = max(d[k], d[x] + 1);
                }
            }
            int mx = 0;
            for(int x = n; x > 0; x--)
            {
                if(blocked[x]) continue;
                mx = max(mx, d[x]);
            }
            cout << mx << "\n";
            for (int x = 1; x <= n; x++)
            {
                d[x] = -1e9;
            }
        }
        else
        {
            for (pair<int, int> p : longest_path[i])
            {
                if (!blocked[p.second])
                {
                    cout << p.first << "\n";
                    break;
                }
            }
        }
        for(int i : c) blocked[i] = 0;
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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