Submission #567305

#	Time	Username	Problem	Language	Result	Execution time	Memory
567305		milisav	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1665 ms	127356 KiB

bitaro

    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("avx,avx2,fma")
     
    #include"bits/stdc++.h"
    using namespace std;
     
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
     
    template<class x>
    using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
     
    #define int long long
    #define endl '\n'
    #define mod 1000000007
    //\
    #define mod 1686876991
     
    const int maxn = 100001;
    const int sq = 71;
     
    vector<int> adj[maxn], radj[maxn];
     
    int n, m, q;
     
    pair<int,int> dp[maxn][sq];
    int dp2[maxn];
    int c[maxn];
    bitset<maxn> rem, inserted;
     
    signed main () {
        cin.tie(0)->sync_with_stdio(0);
        cin >> n >> m >> q;
     
        for (int i = 0 ; i < m ; i++) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            radj[b].push_back(a);
        }
     
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 0 ; j < sq ; j++) dp[i][j] = {-1e9,-1};
            dp[i][0] = {0, i};
        }
        for (int i = 1 ; i <= n ; i++) {
            vector<pair<int,int>> v;
            for (auto k : dp[i]) {
                if (k.second == -1) break;
                v.push_back(k);
            }
            for (int j : radj[i]) {
                for (auto k : dp[j]) {
                    if (k.second == -1) break;
                    v.push_back({k.first + 1, k.second});
                }
            }
     
            sort(v.begin(), v.end(), greater<pair<int,int>>());
     
            // cerr << v.size() << endl;
            for (int idx = 0, j = 0 ; j < v.size() and idx < sq ; j++) {
                if (inserted[v[j].second]) continue;
                inserted[v[j].second] = 1;
                dp[i][idx] = v[j];
                idx++;
            }
            for (int j = 0 ; j < v.size() ; j++) inserted[v[j].second] = 0;
            // cerr << "here\n";
        }
     
        for (int i = 0 ; i < q ; i++) {
            int t, y;
            cin >> t >> y;
            for (int j = 0 ; j < y ; j++) cin >> c[j], rem[c[j]] = 1;
            if (y < sq - 1) {
                for (int j = 0 ; j < sq ; j++) {
                    if (dp[t][j].second == -1) break;
                    if (!rem[dp[t][j].second]) {
                        cout << dp[t][j].first << endl;
                        goto good;
                    }
                }
                cout << -1 << endl;
                good:;
            }
            else {
                for (int j = 1 ; j <= t ; j++) {
                    dp2[j] = (rem[j] ? -1e9 : 0);
                    for (int k : radj[j]) dp2[j] = max(dp2[j], dp2[k] + 1);
                }
                if (dp2[t] < 0) cout << -1 << endl;
                else cout << dp2[t] << endl;
            }
            for (int j = 0 ; j < y ; j++) rem[c[j]] = 0;
        }
    }

Compilation message (stderr)

bitaro.cpp:17:5: warning: multi-line comment [-Wcomment]
   17 |     //\
      |     ^
bitaro.cpp: In function 'int main()':
bitaro.cpp:63:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for (int idx = 0, j = 0 ; j < v.size() and idx < sq ; j++) {
      |                                       ~~^~~~~~~~~~
bitaro.cpp:69:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int j = 0 ; j < v.size() ; j++) inserted[v[j].second] = 0;
      |                              ~~^~~~~~~~~~

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