Submission #1124908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124908		MatteoArcari	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	962 ms	424176 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;


vi uomoragno (
    int n, int m, int q, vi s, vi e, vi t, vi y, vector<vi> c
) {
    int sqr = sqrt(n);
    vector<vector<pair<int, int>>> sus(n);
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        if (s[i] < e[i]) swap(s[i], e[i]);
        adj[s[i]].push_back(e[i]);
    }

    auto bigQuery = [&](int i) -> int {
        vector<int> d(n, -1);
        d[t[i]] = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (d[i] != -1) {
                for (int j : adj[i]) {
                    d[j] = max(d[j], d[i] + 1);
                }
            }
        }
        for (int j : c[i]) {
            d[j] = -1;
        }
        return {*max_element(d.begin(), d.end())};
    };

    vector<int> done(n);
    for (int i = 0; i < n; i++) {
        vector<int> idx(adj[i].size());
        while (sus[i].size() < sqr) {
            pair<int, int> ma = {-1, -1};
            int jma = -1;
            for (int j = 0; j < adj[i].size(); j++) {
                while (idx[j] < sus[adj[i][j]].size() && 
                    done[sus[adj[i][j]][idx[j]].second]
                ) {
                    idx[j]++;
                }
                if (idx[j] < sus[adj[i][j]].size()) {
                    if (sus[adj[i][j]][idx[j]] > ma) {
                        ma = sus[adj[i][j]][idx[j]];
                        jma = j;
                    }
                }
            }
            if (ma.second == -1) break;
            idx[jma]++;
            sus[i].push_back({ma.first + 1, ma.second});
            done[ma.second] = 1;
        }
        sus[i].push_back({0, i});
        for (auto [d, j] : sus[i]) done[j] = 0;
    }

    vi ans(q, -1);
    for (int i = 0; i < q; i++) {
        if (y[i] >= sqr) {
            ans[i] = bigQuery(i);
            continue;
        }
        for (int j : c[i]) {
            done[j] = 1;
        }
        for (auto [d, j] : sus[t[i]]) {
            if (!done[j]) ans[i] = max(ans[i], d);
        }
        for (int j : c[i]) {
            done[j] = 0;
        }
    }
    return ans;
    
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> s(m), e(m);
    for(int i = 0; i < m; i++){
        cin >> s[i] >> e[i];
        s[i]--; 
        e[i]--;
    }

    vector<vector<int>> c(q);
    vector<int> t(q), y(q);
    for (int i = 0; i < q; i++){
        cin >> t[i] >> y[i];
        t[i]--;
        c[i].resize(y[i]);
        for (int j = 0; j < y[i]; j++){
            cin >> c[i][j];
            c[i][j]--;
        }
    }

    vector<int> ans = uomoragno(n, m, q, s, e, t, y, c);
    
    for (int &x : ans) cout << x << '\n';
}

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