Submission #1041241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041241		ThommyDB	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1000 ms	176980 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

bool compare(pair<int, int>& a, pair<int, int>& b){
    return a.second > b.second;
}
 
signed main() {
    int n, m ,q;
    cin >> n >> m >> q;
    vector<vector<int>> adj(n+5);
    int s, e;
    for(int i = 1; i <= m; i++) {
        cin >> s >> e;
        adj[e].push_back(s);
    }
 
    vector<int> pos(n + 5, -1);
    vector<vector<pair<int, int>>> len(n+5);
    for(int i = 1; i < n+1; i++) {
        len[i].push_back({i, 0});
        for (auto u : adj[i]) {
            for (auto x : len[u]) {
                if (pos[x.first] != -1 && x.second+1 > len[i][pos[x.first]].second) len[i][pos[x.first]].second=x.second+1;
                else len[i].push_back({x.first, x.second + 1});
            }
            sort(len[i].begin(), len[i].end(), compare);
            while (len[i].size() > 100) {
                pos[len[i].back().first] = -1;
                len[i].pop_back();
            }
            for(int j = 0; j < len[i].size(); j++) {
                pos[len[i][j].first] = j;
            }
        }
        for(int j = 0; j < len[i].size(); j++) {
            pos[len[i][j].first] = -1;
        }
    }
 
    vector<int> dp(n + 5, -1);
    vector<bool> busy(n+5);
    for(int i = 1; i <q+1; i++) {
        int src, t;
        cin >> src >> t;
        vector<int> c(t);
        for (int j = 0; j < t; j++) {
            cin >> c[j];
            busy[c[j]] = true;
        }
        int ans = -1;
        if (t > 100) {
            for(int j = 1; j < src+1; j++) {
                for (int u : adj[j]) {
                    if (dp[u] != -1 && dp[u]+1 > dp[j]) dp[j]=dp[u]+1;
                }
                if (!busy[j] && dp[j] < 0) dp[j]=0;
                if (j == src) {
                    ans = dp[j];
                    break;
                }
            }
            fill(dp.begin(), dp.begin() + src + 1, -1);
        } else {
            for (auto x : len[src]) {
                if (!busy[x.first]) {
                    ans = x.second;
                    break;
                }
            }
        }
 
        cout << (ans < 0 ? -1 : ans) << "\n";
        for (int u : c) {
            busy[u] = false;
        }
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:33: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]
   33 |             for(int j = 0; j < len[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~
bitaro.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j = 0; j < len[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~

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