oj.uz

Submission #1085312

# Submission time Handle Problem Language Result Execution time Memory
1085312 2024-09-07T23:42:08 Z eysbutno Bitaro’s Party (JOI18_bitaro) C++17
7 / 100
 2000 ms 118872 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 = 100;
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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 6 ms 856 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 12 ms 1468 KB Output is correct
9 Correct 11 ms 1372 KB Output is correct
10 Correct 11 ms 1372 KB Output is correct
11 Correct 12 ms 1332 KB Output is correct
12 Correct 13 ms 1116 KB Output is correct
13 Correct 14 ms 1416 KB Output is correct
14 Correct 9 ms 1116 KB Output is correct
15 Correct 12 ms 1036 KB Output is correct
16 Correct 10 ms 1116 KB Output is correct
17 Correct 11 ms 1148 KB Output is correct
18 Correct 11 ms 1116 KB Output is correct
19 Correct 11 ms 1116 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 6 ms 856 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 12 ms 1468 KB Output is correct
9 Correct 11 ms 1372 KB Output is correct
10 Correct 11 ms 1372 KB Output is correct
11 Correct 12 ms 1332 KB Output is correct
12 Correct 13 ms 1116 KB Output is correct
13 Correct 14 ms 1416 KB Output is correct
14 Correct 9 ms 1116 KB Output is correct
15 Correct 12 ms 1036 KB Output is correct
16 Correct 10 ms 1116 KB Output is correct
17 Correct 11 ms 1148 KB Output is correct
18 Correct 11 ms 1116 KB Output is correct
19 Correct 11 ms 1116 KB Output is correct
20 Correct 1161 ms 2644 KB Output is correct
21 Correct 1147 ms 4180 KB Output is correct
22 Correct 1143 ms 4252 KB Output is correct
23 Correct 1255 ms 4032 KB Output is correct
24 Correct 1822 ms 109800 KB Output is correct
25 Correct 1879 ms 102480 KB Output is correct
26 Correct 1865 ms 102512 KB Output is correct
27 Correct 1394 ms 116560 KB Output is correct
28 Correct 1314 ms 116596 KB Output is correct
29 Correct 1307 ms 116584 KB Output is correct
30 Correct 1467 ms 115876 KB Output is correct
31 Execution timed out 2062 ms 118872 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 6 ms 856 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 12 ms 1468 KB Output is correct
9 Correct 11 ms 1372 KB Output is correct
10 Correct 11 ms 1372 KB Output is correct
11 Correct 12 ms 1332 KB Output is correct
12 Correct 13 ms 1116 KB Output is correct
13 Correct 14 ms 1416 KB Output is correct
14 Correct 9 ms 1116 KB Output is correct
15 Correct 12 ms 1036 KB Output is correct
16 Correct 10 ms 1116 KB Output is correct
17 Correct 11 ms 1148 KB Output is correct
18 Correct 11 ms 1116 KB Output is correct
19 Correct 11 ms 1116 KB Output is correct
20 Correct 1161 ms 2644 KB Output is correct
21 Correct 1147 ms 4180 KB Output is correct
22 Correct 1143 ms 4252 KB Output is correct
23 Correct 1255 ms 4032 KB Output is correct
24 Correct 1822 ms 109800 KB Output is correct
25 Correct 1879 ms 102480 KB Output is correct
26 Correct 1865 ms 102512 KB Output is correct
27 Correct 1394 ms 116560 KB Output is correct
28 Correct 1314 ms 116596 KB Output is correct
29 Correct 1307 ms 116584 KB Output is correct
30 Correct 1467 ms 115876 KB Output is correct
31 Execution timed out 2062 ms 118872 KB Time limit exceeded
32 Halted 0 ms 0 KB -