Submission #797456

#	Time	Username	Problem	Language	Result	Execution time	Memory
797456		Sami_Massah	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	768 ms	150412 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;



const int maxn = 200000 + 12, sq = 100;
int n, m, dp[maxn], best[maxn];
vector <int> bconn[maxn], now;
vector <pair<int, int>> pos[maxn];
bitset <maxn> marked;
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int q;
    cin >> n >> m >> q;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        bconn[b].push_back(a);
    }

    for(int i = 1; i <= n; i++){
        pos[i].push_back(make_pair(0, i));
        marked = 0;
        for(int j: bconn[i]){
            for(auto q: pos[j]){
                best[q.second] = max(best[q.second], q.first + 1);
                marked[q.second] = 1;
                }
        }
        for(int j: bconn[i])
            for(auto q: pos[j]){
                if(!marked[q.second])
                    continue;
              //  cout << i << ' ' << j << endl;
                pos[i].push_back(make_pair(best[q.second], q.second));
              //  cout << pos[i].back().first << ' ' << pos[i].back().second << endl;
                marked[q.second] = 0;
                best[q.second] = 0;
            }
        sort(pos[i].begin(), pos[i].end(), greater<pair<int, int>>());
        while(pos[i].size() > sq)
            pos[i].pop_back();
     //   for(auto j: pos[i])
       //     cout << i << ' ' << j.second << ' ' << j.first << endl;
     //   cout << endl;
    }

    for(int i = 0; i < q; i++){
        int st, len;
        cin >> st >> len;
        now.clear();
        for(int i = 0; i < len; i++){
            int a;
            cin >> a;
            now.push_back(a);
            marked[a] = 1;
        }
        if(len < sq){
            int ans = -1;
            for(int i = 0; i < pos[st].size() && ans == -1; i++)
                if(!marked[pos[st][i].second])
                    ans = pos[st][i].first;
            cout << ans << "\n";
        }
        else{
          //  cout << 'g' << endl;
            for(int i = 1; i <= st; i++){
                dp[i] = -maxn;
                if(!marked[i])
                    dp[i] = 0;
                for(int j: bconn[i])
                    dp[i] = max(dp[i], dp[j] + 1);
           //     cout << i << ' ' << dp[i] << endl;
            }
            if(dp[st] < 0)
                dp[st] = -1;
            cout << dp[st] << "\n";
        }
        for(int a: now)
            marked[a] = 0;

    }



}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:60:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             for(int i = 0; i < pos[st].size() && ans == -1; i++)
      |                            ~~^~~~~~~~~~~~~~~~

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