Submission #384899

#	Time	Username	Problem	Language	Result	Execution time	Memory
384899		ntabc05101	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1666 ms	267424 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;

#define LL long long

const int inf = 1e9 + 9;

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

        int n, m, q; cin >> n >> m >> q;

        vector<int> v_in[n], v_out[n];
        for (int i = 0, u, v; i < m; i++) {
                cin >> u >> v;
                --u, --v;

                v_out[u].push_back(v);
                v_in[v].push_back(u);
        }

        int sqrtn = 5 + sqrt(n);
        int dist[n][sqrtn];
        int at[n][sqrtn];
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < sqrtn; j++) {
                        dist[i][j] = -inf;
                        at[i][j] = 0;
                }
        }

        for (int i = 0; i < n; i++) {
                dist[i][0] = 0;
                at[i][0] = i;
        }

        int tmp_at[sqrtn << 1], tmp_dist[sqrtn << 1];
        bool used[n];
        memset(used, false, sizeof used);
        for (int i = 0; i < n; i++) {
                for (auto& to: v_out[i]) {
                        int left = 0, right = 0;
                        int sz = 0;
                        while (left < sqrtn || right < sqrtn) {
                                if (sz == sqrtn) {
                                        break;
                                }

                                if ((left == sqrtn || dist[i][left] < 0) && (right == sqrtn || dist[to][right] < 0)) {
                                        break;
                                }

                                int _at, _dist;
                                if (right == sqrtn || (left < sqrtn && dist[i][left] + 1 >= dist[to][right])) {
                                        _at = at[i][left];
                                        _dist = dist[i][left] + 1;
                                        left++;
                                }
                                else {
                                        _at = at[to][right];
                                        _dist = dist[to][right];
                                        right++;
                                }
                                if (!used[_at]) {
                                        used[_at] = true;
                                        tmp_at[sz] = _at;
                                        tmp_dist[sz] = _dist;
                                        sz++;
                                }
                        }

                        for (int j = 0; j < sz; j++) {
                                at[to][j] = tmp_at[j];
                                dist[to][j] = tmp_dist[j];
                                used[tmp_at[j]] = false;
                        }
                }
        }

        int dp[n], z[n];
        while (q--) {
                int x, y; cin >> x >> y;
                x--;
                for (int i = 0; i < y; i++) {
                        cin >> z[i];
                        z[i]--;
                        used[z[i]] = true;
                }

                if (y >= sqrtn) {
                        for (int i = 0; i < n; i++) {
                                dp[i] = -inf;
                        }
                        dp[x] = 0;
                        for (int i = x; i >= 0; i--) {
                                for (auto& to: v_in[i]) {
                                        dp[to] = max(dp[to], dp[i] + 1);
                                }
                        }

                        int ret = -1;
                        for (int i = 0; i < n; i++) {
                                if (!used[i]) {
                                        ret = max(ret, dp[i]);
                                }
                        }

                        cout << ret << "\n";
                }
                else {
                        int check = false;
                        for (int i = 0; i < sqrtn; i++) {
                                if (dist[x][i] < 0) {
                                        break;
                                }
                                if (!used[at[x][i]]) {
                                        check = true;
                                        cout << dist[x][i] << "\n";
                                        break;
                                }
                        }
                        if (!check) {
                                cout << "-1\n";
                        }
                }

                for (int i = 0; i < y; i++) {
                        used[z[i]] = false;
                }
        }

        return 0;
}

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