oj.uz

Submission #1085314

# Submission time Handle Problem Language Result Execution time Memory
1085314 2024-09-07T23:44:18 Z eysbutno Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 116052 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

constexpr int B = 75;
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> adj(n);
    vector<int> deg(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        ++deg[v];
    }
    vector<vector<pii>> best(n);
    auto cur = deg;
    queue<int> top;
    for (int i = 0; i < n; i++) {
        if (!cur[i]) { top.push(i); }
    }
    const auto merge = [&](int from, int to) -> void {
        map<int, int> mp;
        for (auto [node, dist] : best[from]) {
            mp[node] = max(mp[node], dist + 1);
        }
        for (auto [node, dist] : best[to]) {
            mp[node] = max(mp[node], dist);
        }
        best[to].clear();
        for (auto [node, dist] : mp) {
            best[to].push_back({node, dist});
        }
        sort(all(best[to]), [&](auto &x, auto &y) -> bool {
            return x[1] > y[1];
        });
        if (sz(best[to]) > B) { best[to].resize(B); }
    };
    while (!top.empty()) {
        int u = top.front(); top.pop();
        if (sz(best[u]) < B) {
            best[u].push_back({u, 0});
        }
        for (int v : adj[u]) {
            merge(u, v);
            if (!(--cur[v])) { top.push(v); }
        }
    }
    const auto check = [&](int t, const set<int> &bad) -> int {
        for (auto [node, dist] : best[t]) {
            if (!bad.count(node)) {
                return dist;
            }
        }
        return -1;
    };
    const auto brute_force = [&](int t, const set<int> &bad) -> int {
        queue<int> q;
        auto cur = deg;
        vector<int> best(n, -1);
        for (int i = 0; i < n; i++) {
            if (!cur[i]) { q.push(i); }
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (!bad.count(u)) { best[u] = max(0, best[u]); }
            if (u == t) { break; }
            for (int v : adj[u]) {
                if (best[u] != -1) { best[v] = max(best[v], best[u] + 1); }
                if (!--cur[v]) { q.push(v); }
            }
        }
        return best[t];
    };
    while (q--) {
        int t, y;
        cin >> t >> y;
        --t;
        set<int> bad;
        for (int i = 0; i < y; i++) {
            int x; cin >> x;
            bad.insert(--x);
        }
        if (y >= B) {
            cout << brute_force(t, bad) << "\n";
        } else {
            cout << check(t, bad) << "\n";
        }
    }
    /*
    for (int i = 0; i < n; i++) {
        cout << "node " << i + 1 << "\n";
        for (auto [node, dist] : best[i]) {
            cout << node + 1 << " " << dist << "\n";
        }
    }
    */
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 6 ms 948 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 6 ms 900 KB Output is correct
8 Correct 9 ms 1372 KB Output is correct
9 Correct 8 ms 1372 KB Output is correct
10 Correct 9 ms 1388 KB Output is correct
11 Correct 10 ms 1408 KB Output is correct
12 Correct 11 ms 1116 KB Output is correct
13 Correct 10 ms 1436 KB Output is correct
14 Correct 8 ms 1116 KB Output is correct
15 Correct 10 ms 860 KB Output is correct
16 Correct 8 ms 1116 KB Output is correct
17 Correct 8 ms 1116 KB Output is correct
18 Correct 9 ms 916 KB Output is correct
19 Correct 9 ms 1300 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 6 ms 948 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 6 ms 900 KB Output is correct
8 Correct 9 ms 1372 KB Output is correct
9 Correct 8 ms 1372 KB Output is correct
10 Correct 9 ms 1388 KB Output is correct
11 Correct 10 ms 1408 KB Output is correct
12 Correct 11 ms 1116 KB Output is correct
13 Correct 10 ms 1436 KB Output is correct
14 Correct 8 ms 1116 KB Output is correct
15 Correct 10 ms 860 KB Output is correct
16 Correct 8 ms 1116 KB Output is correct
17 Correct 8 ms 1116 KB Output is correct
18 Correct 9 ms 916 KB Output is correct
19 Correct 9 ms 1300 KB Output is correct
20 Correct 895 ms 2748 KB Output is correct
21 Correct 871 ms 2776 KB Output is correct
22 Correct 864 ms 2640 KB Output is correct
23 Correct 962 ms 2724 KB Output is correct
24 Correct 1371 ms 89940 KB Output is correct
25 Correct 1411 ms 90452 KB Output is correct
26 Correct 1386 ms 90448 KB Output is correct
27 Correct 980 ms 113992 KB Output is correct
28 Correct 980 ms 114004 KB Output is correct
29 Correct 1028 ms 114000 KB Output is correct
30 Correct 1085 ms 113472 KB Output is correct
31 Correct 1669 ms 111696 KB Output is correct
32 Correct 1095 ms 116052 KB Output is correct
33 Correct 786 ms 80052 KB Output is correct
34 Correct 1396 ms 91580 KB Output is correct
35 Correct 784 ms 79608 KB Output is correct
36 Correct 899 ms 98124 KB Output is correct
37 Correct 1568 ms 93520 KB Output is correct
38 Correct 912 ms 98112 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 6 ms 948 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 6 ms 900 KB Output is correct
8 Correct 9 ms 1372 KB Output is correct
9 Correct 8 ms 1372 KB Output is correct
10 Correct 9 ms 1388 KB Output is correct
11 Correct 10 ms 1408 KB Output is correct
12 Correct 11 ms 1116 KB Output is correct
13 Correct 10 ms 1436 KB Output is correct
14 Correct 8 ms 1116 KB Output is correct
15 Correct 10 ms 860 KB Output is correct
16 Correct 8 ms 1116 KB Output is correct
17 Correct 8 ms 1116 KB Output is correct
18 Correct 9 ms 916 KB Output is correct
19 Correct 9 ms 1300 KB Output is correct
20 Correct 895 ms 2748 KB Output is correct
21 Correct 871 ms 2776 KB Output is correct
22 Correct 864 ms 2640 KB Output is correct
23 Correct 962 ms 2724 KB Output is correct
24 Correct 1371 ms 89940 KB Output is correct
25 Correct 1411 ms 90452 KB Output is correct
26 Correct 1386 ms 90448 KB Output is correct
27 Correct 980 ms 113992 KB Output is correct
28 Correct 980 ms 114004 KB Output is correct
29 Correct 1028 ms 114000 KB Output is correct
30 Correct 1085 ms 113472 KB Output is correct
31 Correct 1669 ms 111696 KB Output is correct
32 Correct 1095 ms 116052 KB Output is correct
33 Correct 786 ms 80052 KB Output is correct
34 Correct 1396 ms 91580 KB Output is correct
35 Correct 784 ms 79608 KB Output is correct
36 Correct 899 ms 98124 KB Output is correct
37 Correct 1568 ms 93520 KB Output is correct
38 Correct 912 ms 98112 KB Output is correct
39 Correct 1391 ms 93012 KB Output is correct
40 Correct 1355 ms 92324 KB Output is correct
41 Execution timed out 2055 ms 93020 KB Time limit exceeded
42 Halted 0 ms 0 KB -