Submission #1124904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124904		LaMatematica14	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	7 ms	836 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int lim = 10000000;
const int rad = 400;
int N;
vector<vector<int>> adj;
vector<vector<pair<int, int>>> dp;

void crea(int a) {
    priority_queue<pair<int, int>> pq;
    unordered_set<int> pr;
    for (int x : adj[a]) {
        pq.push({1, x});
        for (auto j : dp[x]) pq.push({j.first+1, j.second});
    }
    int h = 0;
    while (h < rad && !pq.empty()) {
        auto aus = pq.top(); pq.pop();
        if (pr.count(aus.second)) continue;
        dp[a].push_back(aus);
        pr.insert(aus.second);
        h++;
    }
}

int bfs(int a, unordered_set<int> skip) {
    queue<int> n;
    vector<int> dist(N);
    dp.resize(N);
    fill(dist.begin(), dist.end(), lim);
    dist[a] = 0; n.push(a);
    int m = -1;
    while (!n.empty()) {
        a = n.front(); n.pop();
        if (!skip.count(a)) m = max(m, dist[a]);
        for (int x : adj[a]) {
            if (dist[x] < lim) continue;
            dist[x] = dist[a]+1;
            n.push(x);
        }
    }
    return m;
}

int prec(int a, unordered_set<int> s) {
    int m = -1;
    if (!s.count(a)) m = 0;
    for (int i = 0; i < dp[a].size(); i++) {
        if (s.count(dp[a][i].second)) continue;
        m = max(m, dp[a][i].first);
    }
    return m;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    int M, Q; cin >> N >> M >> Q;
    adj.resize(N+1);
    for (int i = 0; i < M; i++) {
        int s, t; cin >> s >> t;
        adj[t].push_back(s);
    }
    dp.resize(N+1);
    for (int i = 1; i <= N; i++) crea(i);
    for (int i = 0; i < Q; i++) {
        int a; cin >> a >> M;
        unordered_set<int> s;
        for (int j = 0; j < M; j++) {
            int aus; cin >> aus; s.insert(aus);
        }
        if (M >= rad) cout << bfs(a, s) << "\n";
        else cout << prec(a, s) << "\n";
    }
}

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