Submission #1321525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321525		askeww	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1591 ms	253724 KiB

bitaro

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,lzcnt,popcnt,bmi2,sse4.2")

template<typename T>
using V = vector<T>;
using pi = pair<int, int>;

const int B = 100;

int n, m, q, s, e, ans;
V<V<int>> l, r, c;
V<unordered_map<int, int>> d; // i -> d
V<V<pi>> st; // [d, i]
V<int> t, y;
V<bool> dis;

int main() {
    cin >> n >> m >> q;

    r = l = V<V<int>>(n + 1);
    for (int i = 1; i <= m; i++) {
        cin >> s >> e;

        r[s].push_back(e);
        l[e].push_back(s);
    }

    t = y = V<int>(q + 1);
    c = V<V<int>>(q + 1);
    for (int i = 1; i <= q; i++) {
        cin >> t[i] >> y[i];
        for (int j = 1; j <= y[i]; j++) {
            cin >> s;
            c[i].push_back(s);
        }
        sort(c[i].begin(), c[i].end());
    }

    d = V<unordered_map<int, int>>(n + 1);
    st = V<V<pi>>(n + 1);
    for (int j = 1; j <= n; j++) {
        st[j].push_back({0, j});
        for (auto& k : l[j]) {
            for (auto& it : st[k]) {
                st[j].push_back({it.first + 1, it.second});
            }
        }

        unordered_map<int, int> um;
        for (auto& it : st[j]) um[it.second] = max(um[it.second], it.first);
        st[j] = {};
        for (auto& it : um) {
            st[j].push_back({it.second, it.first});
        }
        sort(st[j].begin(), st[j].end(), [](const pi& a, const pi& b) {
            return a.first > b.first;
        });
        while (st[j].size() > B) st[j].pop_back();
    }

    dis = V<bool>(n + 1);
    for (int i = 1; i <= q; i++) {
        int x = t[i];
        if (y[i] >= B) {
            V<int> f(n + 1, 0);
            for (auto& j : c[i]) f[j] = -1;
            for (int j = 1; j <= x; j++) {
                for (auto& k : l[j]) 
                    if (f[k] != -1) f[j] = max(f[j], f[k] + 1);
            }
            cout << f[x] << " ";
        } else {

            for (int j : c[i]) dis[j] = true;
            bool done = false;
            for (pi it : st[x]) {
                if (!dis[it.second]) {
                    cout << it.first << " ";
                    done = true;
                    break;
                }
            }
            if (!done) cout << "-1 ";
            for (int j : c[i]) dis[j] = false;
        }
    }
}

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