Submission #1012282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012282		MohamedFaresNebili	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2061 ms	12744 KiB

bitaro

#include <bits/stdc++.h>

        using namespace std;

        const int batch = 320;

        int N, M, Q;
        int D[100005];
        vector<int> rev[100005];
        vector<pair<int, int>> farthest[100005];
        bool rem[100005], vis[100005];

        bool comp(int U, int V) {
            return D[U] > D[V];
        }

        int32_t main() {
            ios_base::sync_with_stdio(0);
            cin.tie(0); cout.tie(0);
            cin >> N >> M >> Q;
            for(int l = 0; l < M; l++) {
                int S, E; cin >> S >> E;
                rev[E].push_back(S);
            }
            for(int l = 1; l <= N; l++) {
                vector<int> V;
                for(auto u : rev[l]) {
                    for(auto e : farthest[u]) {
                        int dist = e.second + 1;
                        if(vis[e.first] != l) {
                            vis[e.first] = l; V.push_back(e.first);
                            D[e.first] = dist;
                        }
                        else D[e.first] = max(D[e.first], dist);
                    }
                    if(vis[u] != l) {
                        vis[u] = l; V.push_back(u);
                        D[u] = 1;
                    }
                }
                V.push_back(l); sort(V.begin(), V.end(), comp);
                for(int i = 0; i < V.size() && i < batch; i++) {
                    farthest[l].push_back({V[i], D[V[i]]});
                }
            }
            while(Q--) {
                int T, Y; cin >> T >> Y;
                vector<int> att;
                for(int l = 0; l < Y; l++) {
                    int A; cin >> A;
                    att.push_back(A);
                    rem[A] = 1;
                }

                if(Y < batch) {
                    bool ok = false;
                    for(auto u : farthest[T]) {
                        if(rem[u.first]) continue;
                        cout << u.second << "\n";
                        ok = true; break;
                    }
                    if(ok == false)
                        cout << -1 << "\n";
                }
                else {
                    vector<int> dp(N + 1, -1);
                    for(int l = 1; l <= T; l++) {
                        if(!rem[l]) dp[l] = max(dp[l], 0);
                        for(auto u : rev[l]) {
                            if(dp[u] != -1) dp[l] = max(dp[l], dp[u] + 1);
                        }
                    }
                    cout << dp[T] << "\n";
                }
                for(auto u : att) rem[u] = 0;

            }
            return 0;
        }

Compilation message (stderr)

bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:42:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                 for(int i = 0; i < V.size() && i < batch; i++) {
      |                                ~~^~~~~~~~~~

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