Submission #1128932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128932		antonn	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1787 ms	422616 KiB

bitaro

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const int K = 320;


int n, m, q;
vector<vector<int>> g, gg;
vector<vector<pair<int, int>>> closest;
vector<int> vis, ord, dp;


void dfs(int u) {
    vis[u] = 1;
    for (auto v : g[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
    ord.push_back(u);
}


vector<bool> in;


void merge(vector<pair<int, int>> &a, vector<pair<int, int>> b) {
    for (int i = 0; i < b.size(); i += 1) {
        b[i].first += 1;
    }
    vector<pair<int, int>> c;
    int i = 0;
    int j = 0;
    while (i < a.size() || j < b.size()) {
        if (i == a.size()) {
            c.push_back(b[j]);
            j += 1;
            continue;
        }
        if (j == b.size()) {
            c.push_back(a[i]);
            i += 1;
            continue;
        }
        if (a[i].first >= b[j].first) {
            c.push_back(a[i]);
            i += 1;
            continue;
        } else {
            c.push_back(b[j]);
            j += 1;
            continue;
        }
    }
    vector<pair<int, int>> f;
    for (int i = 0; i < c.size(); i += 1) {
        if (in[c[i].second] == 1) {
            continue;
        }
        f.push_back({c[i].first, c[i].second});
        in[c[i].second] = 1;
        if (f.size() > K) {
            break;
        }
    }
    for (auto [x, y] : f) {
        in[y] = 0;
    }
    swap(a, f);
}




void dfs2(int u) {
    vis[u] = 1;
    for (auto v : gg[u]) {
        if (dp[u] + 1 > dp[v]) {
            dp[v] = max(dp[v], dp[u] + 1);
            dfs2(v);
        }
    }
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
	}
	cin >> n >> m >> q;
    g.resize(n + 1);
    gg.resize(n + 1);
    for (int i = 1; i <= m; i += 1) {
        int e, s;
        cin >> e >> s;
        g[e].push_back(s);
        gg[s].push_back(e);
    }
    vis.assign(n + 1, 0);
    for (int i = 1; i <= n; i += 1) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    in.resize(n + 1);
    reverse(all(ord));
    closest.resize(n + 1);
    int when = 0;
    for (auto i : ord) {
        closest[i].push_back({0, i});
        for (auto v : gg[i]) {
            merge(closest[i], closest[v]);
        }
    }
   
    dp.resize(n + 1);
    vector<int> blocked(n + 1, 0);
    for (int iq = 1; iq <= q; iq += 1) {
        int t, y;
        cin >> t >> y;
        vector<int> v;
        for (int j = 0; j < y; j += 1) {
            int x;
            cin >> x;
            v.push_back(x);
            blocked[x] = 1;
        }
        if (y > K) {
            for (int i = 1; i <= n; i += 1) {
                dp[i] = -1e9;
            }
            dp[t] = 0;
            for (int i = t; i >= 1; i -= 1) {
                for (auto j : gg[i]) {
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
            int ans = -1;
            for (int i = 1; i <= n; i += 1) {
                if (blocked[i] == 0) {
                    ans = max(ans, dp[i]);
                }
            }
            cout << ans << "\n";
        } else {
            int ans = -1;
            for (auto i : closest[t]) {
                if (!blocked[i.second]) {
                    ans = i.first;
                    break;
                }
            }
            cout << ans << "\n";
        }
        for (auto i : v) {
            blocked[i] = 0;
        }
    }
    return 0;
}

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