Submission #988452

#	Time	Username	Problem	Language	Result	Execution time	Memory
988452		ortsac	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1568 ms	263284 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

int block = 316;
#define pii pair<int, int>
#define fr first
#define se second

vector<vector<pii>> far;
vector<bool> freq;
pii aux[500];

void merge(int from, int to) {
    vector<pii> leaving;
    for (auto u : far[from]) {
        leaving.push_back({u.fr + 1, u.se});
    }
    for (auto u : leaving) {
        freq[u.se] = 0;
    }
    for (auto u : far[to]) {
        freq[u.se] = 0;
    }
    int p1 = 0, p2 = 0;
    int n = leaving.size();
    int m = far[to].size();
    int s = 0;
    while ((s < block) && ((p1 < n) || (p2 < m))) {
        if (p1 == n) {
            // check p2
            if (freq[far[to][p2].se]) {
                p2++;
                continue;
            }
            aux[s] = far[to][p2];
            freq[far[to][p2].se] = 1;
            p2++;
        } else if (p2 == m) {
            // check p1
            if (freq[leaving[p1].se]) {
                p1++;
                continue;
            }
            aux[s] = leaving[p1];
            freq[leaving[p1].se] = 1;
            p1++;
        } else {
            if (freq[leaving[p1].se]) {
                p1++;
                continue;
            }
            if (freq[far[to][p2].se]) {
                p2++;
                continue;
            }
            if (leaving[p1] > far[to][p2]) {
                aux[s] = leaving[p1];
                freq[leaving[p1].se] = 1;
                p1++;
            } else {
                aux[s] = far[to][p2];
                freq[far[to][p2].se] = 1;
                p2++;
            }
        }
        s++;
    }
    far[to].resize(s);
    for (int i = 0; i < s; i++) {
        far[to][i] = aux[i];
    }
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
    }
    far.resize(n + 1);
    freq.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        far[i].push_back({0, i});
    }
    for (int i = 1; i <= n; i++) {
        for (auto u : adj[i]) {
            merge(i, u);
        }
    }
    while (q--) {
        int t, y;
        cin >> t >> y;
        if (y >= block) {
            vector<int> mx(n + 1);
            while (y--) {
                int a;
                cin >> a;
                mx[a] = -1;
            }
            for (int i = 1; i <= t; i++) {
                if (mx[i] == -1) continue;
                for (auto u : adj[i]) {
                    mx[u] = max(mx[u], mx[i] + 1);
                }
            }
            cout << mx[t] << "\n";
        } else {
            unordered_map<int, bool> map;
            while (y--) {
                int a;
                cin >> a;
                map[a] = 1;
            }
            bool good = 0;
            for (auto u : far[t]) {
                if (!map[u.se]) {
                    cout << u.fr << "\n";
                    good = 1;
                    break;
                }
            }
            if (!good) {
                cout << "-1\n";
            }
        }
    }
}

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