Submission #1321516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321516		askeww	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	1942 ms	589824 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;
V<set<int>> c;
V<unordered_map<int, int>> d; // i -> d
V<set<pi>> st; // [d, i]
V<int> t, y;

void add(int j, pi p) {
    if (d[j].count(p.second)) {
        if (p.first > d[j][p.second]) {
            assert(st[j].find({d[j][p.second], p.second}) != st[j].end());
            st[j].erase({d[j][p.second], p.second});
            d[j][p.second] = p.first;
            st[j].insert(p);
        }
        return;
    }

    d[j][p.second] = p.first;
    st[j].insert(p);
    if (st[j].size() > B) {
        auto del = st[j].begin();
        assert(d[j].count(del->second));
        d[j].erase(del->second);
        st[j].erase(del);
    }
}

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<set<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].insert(s);
        }
    }

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

    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 {
            bool done = false;
            for (auto it = st[x].rbegin(); it != st[x].rend(); it++) {
                if (c[i].find(it->second) == c[i].end()) {
                    cout << it->first << " ";
                    done = true;
                    break;
                }
            }
            if (!done) cout << "-1 ";
        }
    }
}

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