Submission #559604

#	Time	Username	Problem	Language	Result	Execution time	Memory
559604		Kaipalo	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1963 ms	415300 KiB

bitaro

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

const int sqrt = 500;
int n, m, q;
vector <int> parent[100005];

struct st {
    int idx, d;
    bool operator < (const st &other) const {
        return d > other.d;
    }
};

vector <int> canGo;
vector <st> dist[100005], all;
st visited[100005];
int busy[100005], dp[100005];


int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        parent[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        canGo.clear();
        all.clear();
        canGo.push_back(i);
        visited[i] = {i, 0};

        for (auto p : parent[i]) {
            for (auto go : dist[p]) {
                if (visited[go.idx].idx != i) {
                    visited[go.idx] = {i, 1 + go.d};
                    canGo.push_back(go.idx);
                }
                else {
                    if (visited[go.idx].d < 1 + go.d) {
                        visited[go.idx].d = 1 + go.d;
                    }
                }
            }
        }

        for (auto go : canGo) {
            all.push_back({go, visited[go].d});
        }

        sort(all.begin(), all.end());
        for (int j = 0; j < min((int)all.size(), sqrt); j++) {
            dist[i].push_back(all[j]);
        }
    }


    for (int i = 1; i <= q; i++) {
        int t, y; cin >> t >> y;
        for (int j = 0; j < y; j++) {
            int x; cin >> x;
            busy[x] = i;
        }

        if (y < sqrt) {
            bool found = false;
            for (auto e : dist[t]) {
                if (busy[e.idx] != i) {
                    cout << e.d << '\n';
                    found = true;
                    break;
                }
            }

            if (!found) cout << -1 << '\n';
        }
        else {
            memset(dp, -1, sizeof(dp));
            for (int j = 1; j <= t; j++) {
                if (busy[j] != i) dp[j] = 0;

                for (auto p : parent[j]) {
                    if (dp[p] == -1) continue;
                    else dp[j] = max(dp[j], dp[p] + 1);
                }

            }

            cout << dp[t] << '\n';
        }
    }



    return 0;
}

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