Submission #531127

#	Time	Username	Problem	Language	Result	Execution time	Memory
531127		4fecta	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	16 ms	30408 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 200005;

int n, m, q, u, v, k, dp[MN], ans[MN];
vector<int> a[MN], r[MN], nodes[MN];
vector<vector<int>> qs[MN];
bitset<100005> reach[100005];

int32_t main() {
    boost();

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        a[u].push_back(v);
        r[v].push_back(u);
    }
    for (int i = 1; i <= q; i++) {
        cin >> u >> k;
        vector<int> vec = {i};
        for (int j = 1; j <= k; j++) cin >> v, vec.push_back(v);
        qs[u].push_back(vec);
    }
    for (int i = 1; i <= n; i++) {
        dp[i] = 0;
        nodes[i] = {i};
        reach[i][i] = 1;
        for (int j : r[i]) {
            if (dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                nodes[i] = nodes[j];
            } else if (dp[j] + 1 == dp[i]) {
                for (int p : nodes[j]) nodes[i].push_back(p);
            }
        }
        sort(nodes[i].begin(), nodes[i].end());
        nodes[i].erase(unique(nodes[i].begin(), nodes[i].end()), nodes[i].end());
        for (int j : r[i]) if (dp[j] + 1 == dp[i]) reach[i] |= reach[j];
        for (auto qu : qs[i]) {
            set<int> s;
            for (int j = 1; j < qu.size(); j++) s.insert(qu[j]);
            vector<pii > vec;
            int ret = -1;
            for (int p : nodes[i]) {
                if (!s.count(p)) {ret = dp[i]; break;}
                else vec.push_back({p, dp[i]});
            }
            while (vec.size() && ret == -1) {
                vector<pii> w;
                for (pii p : vec) {
                    for (int nxt : a[p.f]) {
                        if (!reach[i][nxt]) continue;
                        if (!s.count(nxt)) {ret = p.s - 1; break;}
                        else w.push_back({nxt, p.s - 1});
                    }
                    if (ret != -1) break;
                }
                vec = w;
            }
            ans[qu[0]] = ret;
        }
    }
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:51:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for (int j = 1; j < qu.size(); j++) s.insert(qu[j]);
      |                             ~~^~~~~~~~~~~

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