Submission #1280334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280334		MinhKien	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	889 ms	418732 KiB

bitaro

#include <iostream>
#include <vector>

using namespace std;

#define ii pair <int, int>
#define fi first
#define se second

const int N = 1e5 + 10;
const int BlockSize = 350;

int n, m, k;
int x, y;
vector <int> g[N];
vector <ii> mx[N];

struct query {
    int st, num;
    vector <int> v;
} q;

bool used[N], busy[N];
vector <ii> combine(const vector <ii> &A, const vector <ii> &B) {
    vector <ii> res;
    res.clear();
    int i = 0, j = 0;
    while (i < A.size() || j < B.size()) {
        if (res.size() == BlockSize) break;

        if (j == B.size() || (i < A.size() && A[i].fi + 1 > B[j].fi)) {
            if (!used[A[i].se]) {
                res.push_back(ii(A[i].fi + 1, A[i].se));
                used[A[i].se] = true;
            }
            ++i;
        } else {
            if (!used[B[j].se]) {
                res.push_back(B[j]);
                used[B[j].se] = true;
            }
            ++j;
        }
    }

    for (ii z: res) used[z.se] = false;

    return res;
}

vector <int> need;
bool tham[N];
int curans[N];

void solve(int s) {
    tham[s] = true;
    need.push_back(s);
    curans[s] = 0;
    for (int z: g[s]) {
        if (!tham[z]) solve(z);
        curans[s] = max(curans[s], curans[z] + 1);
    }
    if (curans[s] == 0 && busy[s]) curans[s] = -1e9;
}

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

    cin >> n >> m >> k;
    while (m--) {
        cin >> x >> y;
        g[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i) {
        mx[i].push_back(ii(0, i));
        for (int z: g[i]) {
            mx[i] = combine(mx[z], mx[i]);
        }
    }

    while (k--) {
        cin >> q.st >> q.num;
        q.v.clear();
        q.v.resize(q.num);
        for (int &z: q.v) {
            cin >> z;
            busy[z] = true;
        }

        if (q.num < BlockSize) {
            int i = 0;
            while (i < mx[q.st].size() && busy[mx[q.st][i].se]) ++i;
            if (i < mx[q.st].size()) cout << mx[q.st][i].fi << "\n";
            else cout << "-1\n";
        } else {
            solve(q.st);
            if (curans[q.st] < 0) curans[q.st] = -1;
            cout << curans[q.st] << "\n";

            for (int z: need) tham[z] = false;
            need.clear();
        }

        for (int z: q.v) busy[z] = false;
    }

    return 0;
}

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