Submission #1342863

#TimeUsernameProblemLanguageResultExecution timeMemory
1342863nagorn_phBitaro’s Party (JOI18_bitaro)C++20
100 / 100
1687 ms217228 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

// #define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));

const int mod = 1e9 + 7;
const int inf = 1e18;
const matrix II = {{1, 0}, {0, 1}};
const int N = 2e5 + 5;

void solve(){
    int n, m, q; cin >> n >> m >> q; int sq = 150;
    vector <int> adj[n + 1], radj[n + 1];
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u].emb(v);
        radj[v].emb(u);
    }
    vector <pii> dp[n + 1];
    vector <int> visited(n + 1);
    for (int u = 1; u <= n; u++) {
        vector <pii> cur;
        for (auto v : radj[u]) {
            cur.emb(1, v);
            for (auto [dis, node] : dp[v]) {
                cur.emb(dis + 1, node);
            }
        }
        sort(rall(cur));
        for (auto [dis, node] : cur) {
            if (visited[node] == u) continue;
            visited[node] = u;
            dp[u].emb(dis, node);
            if (dp[u].size() == sq) break;
        }
    }
    vector <int> cant(n + 1, inf);
    int cnt = 0;
    while (q--) {
        int st, y; cin >> st >> y;
        // cout << ++cnt << " : ";
        for (int i = 1; i <= y; i++) {
            int x; cin >> x;
            cant[x] = q;
        }
        if (y <= sq) {
            int ans = (cant[st] == q ? -1 : 0);
            for (auto [dis, node] : dp[st]) {
                if (cant[node] == q) continue;
                ans = max(ans, dis);
            }
            // cout << "SQ : ";
            cout << ans << "\n";
        }
        else {
            vector <int> mx(n + 1, -inf);
            for (int u = 1; u <= st; u++) {
                if (cant[u] != q) mx[u] = 0;
                for (auto v : radj[u]) {
                    mx[u] = max(mx[u], mx[v] + 1);
                }
            }
            cout << (mx[st] < 0 ? -1ll : mx[st]) << "\n";
        }
    }
}

int32_t main(){
    iShowSpeed;
    // int q; cin >> q; while (q--) 
    solve();
}

Compilation message (stderr)

bitaro.cpp:24:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   24 | const int inf = 1e18;
      |                 ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...