Submission #1280179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280179		MinhKien	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2 ms	580 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 = 320;

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

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

bool kk[N];
void DFS(int s) {
    kk[s] = true;
    vis.push_back(s);
    for (int z: g[s]) {
        --dag[z];
        if (dag[z] == 0) DFS(z);
    }
}

bool used[N];
vector <ii> combine(vector <ii> &A, vector <ii> &B) {
    vector <ii> res;
    int i = 0, j = 0;
    while ((i < A.size() || j < B.size()) && res.size() < BlockSize) {
        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(ii(B[j].fi, B[j].se));
                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 (used[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);
        ++dag[x];
    }

    for (int i = 1; i <= n; ++i) {
        if (!kk[i] && !dag[i]) DFS(i);
    }

    for (int i = n; i >= 1; --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.resize(q.num);
        for (int &z: q.v) {
            cin >> z;
            used[z] = true;
        }

        if (q.num <= BlockSize) {
            int i = 0;
            while (i < mx[q.st].size() && used[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) used[z] = false;
    }

    return 0;
}

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