Submission #1301860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301860		Owstin	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	573 ms	110768 KiB

bitaro

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define pb push_back
#define all(x) begin(x), end(x)
#define umap unordered_map
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int b, c, d; cin >> b >> c >> d;
    int block = 100;
    vector<vector<int>> adj(b + 1);
    for (int i = 0; i < c; i++) {
        int x, y; cin >> x >> y;
        adj[y].pb(x);
    }
    vector<vector<pair<int, int>>> keeps(b + 1);
    vector<bool> visited(b + 1);
    for (int i = 1; i <= b; i++) {
        priority_queue<pair<pair<int, int>, int>> pq;
        for (int j = 0; j < adj[i].size(); j++) {
            pq.push({{keeps[adj[i][j]][0].first, 0}, adj[i][j]});
        }
        for (int j = 0; j < block; j++) {
            if (pq.empty()) {
                break;
            }
            auto curr = pq.top(); pq.pop();
            int dist = curr.first.first; int pos = curr.first.second; int node = curr.second;
            if (!visited[keeps[node][pos].second]) {
                keeps[i].pb({dist + 1, keeps[node][pos].second});
                visited[keeps[node][pos].second] = true;
            }
            else {
                j--;
            }
            if (pos != keeps[node].size() - 1) {
                pq.push({{keeps[node][pos + 1].first, pos + 1}, node});
            }
        }
        for (auto x : keeps[i]) {
            visited[x.second] = false;
        }
        if (keeps[i].size() != block) {
            keeps[i].pb({0, i});
        }
    }
    while (d--) {
        int node; cin >> node;
        int n; cin >> n;
        vector<int> vec(n);
        for (int i = 0; i < n; i++) {
            cin >> vec[i];
            visited[vec[i]] = true;
        }
        if (n >= block) {
            vector<int> large(node + 1, INT32_MIN);
            for (int i = 1; i <= node; i++) {
                if (!visited[i]) {
                    large[i] = max(large[i], 0);
                }
                for (int j = 0; j < adj[i].size(); j++) {
                    large[i] = max(large[i], large[adj[i][j]] + 1);
                }
            }
            cout << (large[node] >= 0 ? large[node] : -1) << endl;
        }
        else {
            bool flag = false;
            for (int i = 0; i < keeps[node].size(); i++) {
                if (!visited[keeps[node][i].second]) {
                    cout << keeps[node][i].first << endl;
                    flag = true; break;
                }
            }
            if (!flag) {
                cout << -1 << endl;
            }
        }
        for (int i = 0; i < n; i++) {
            visited[vec[i]] = false;
        }
    }
}

int main() {
    FAST_IO;
    //freopen("cowmbat.in", "r", stdin);
    //freopen("cowmbat.out", "w", stdout);
    //TEST_CASES;
    solve(); cout << endl;
    /*int a; cin >> a;
    for (int i = 1; i <= a; i++){
        cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }*/
}

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