Submission #426641

#	Time	Username	Problem	Language	Result	Execution time	Memory
426641		tengiz05	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	2 ms	332 KiB

bitaro

#include <bits/stdc++.h>
struct segtree{
    int n;
    std::vector<int> t;
    segtree(int n) : n(n), t(2 * n, 0) { }
    void update(int p, int val) {
        for (t[p += n] += val; p > 1; p >>= 1) {
            t[p >> 1] = std::min(t[p], t[p ^ 1]);
        }
    }
    int get(int l, int r) {
        int res = 1e9;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l % 2 == 1) res = std::min(res, t[l++]);
            if (r % 2 == 0) res = std::min(res, t[r--]);
        }
        return res;
    }
};
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::vector<int>> e(n), p(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        e[u].push_back(v);
        p[v].push_back(u);
    }
    std::vector<int> dp(n);
    segtree seg(n);
    for (int u = 0; u < n; u++) {
        for (auto v : p[u]) {
            dp[u] = std::max(dp[u], dp[v] + 1);
        }
        seg.update(u, dp[u]);
    }
    while (q--) {
        int t, k;
        std::cin >> t >> k;
        t--;
        std::vector<int> c(k);
        for (int i = 0, x; i < k; i++) {
            std::cin >> c[i];
            c[i]--;
            seg.update(c[i], 1e9);
        }
        int ans = std::max(-1, dp[t] - seg.get(0, t));
        std::cout << ans << "\n";
        for (auto x : c) {
            seg.update(x, -1e9);
        }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:47:25: warning: unused variable 'x' [-Wunused-variable]
   47 |         for (int i = 0, x; i < k; i++) {
      |                         ^

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