Submission #829390

#	Time	Username	Problem	Language	Result	Execution time	Memory
829390		vjudge1	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	979 ms	524288 KiB

bitaro

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 100100;
const int SQ = 316;

vector < int > adj[N], dp(N), use(N);
vector < pair < int, int > > calc[N];
queue < pair < int, int > > q;

int True;

void merge(vector < pair < int, int > >  &A, vector < pair < int, int > > &B) {
    ++ True;
    for(int i = 0, j = 0; q.size() < SQ;) {
        for(; i < A.size() && use[A[i].first] == True; ++ i);
        for(; j < B.size() && use[B[j].first] == True; ++ j);
        if(i == A.size() && j == B.size()) {
            break;
        }
        if(j == B.size() || (i < A.size() && B[j].second < A[i].second)) {
            q.push(A[i]);
            use[A[i].first] = True;
            ++ i;
        } else {
            ++ B[j].second;
            q.push(B[j]);
            -- B[j].second;
            use[B[j].first] = True;
            ++ j;
        }
    }
    A.resize(q.size());
    for(int i = 0; i < A.size(); ++ i) {
        A[i] = q.front();
        q.pop();
    }
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, Q, u, v;
    for(cin >> n >> m >> Q; m --> 0;) {
        cin >> u >> v;
        adj[u].push_back(v);
    }
    for(int i = 1; i <= n; ++ i) {
        calc[i].push_back({i, 0});
        for(auto &j : adj[i]) {
            merge(calc[j], calc[i]);
        }
    }
    /**
    for(int i = 1; i <= n; ++ i) {
        cout << i << "\n";
        for(auto &[from, dist] : calc[i]) {
            cout << from << " ---- " << dist << '\n';
        }
        cout << "\n\n\n";
    }
    // */
    for(int T, Y, C, tt; Q --> 0;) {
        ++ True;
        for(cin >> T >> Y, tt = Y; tt --> 0;) {
            cin >> C;
            use[C] = True;
        }
        if(Y < SQ) {
            int i = 0;
            for(; i < calc[T].size() && use[calc[T][i].first] == True; ++ i);
            cout << (i == calc[T].size() ? -1 : calc[T][i].second) << '\n';
        } else {
            for(int i = 0; i < n; dp[++ i] = -1);
            for(int i = 1; i <= n; ++ i) {
                dp[i] += use[i] != True || dp[i] != -1;
                for(auto &j : adj[i]) {
                    dp[j] = max(dp[j], dp[i]);
                }
            }
            cout << dp[T] << '\n';
        }
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'void merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(; i < A.size() && use[A[i].first] == True; ++ i);
      |               ~~^~~~~~~~~~
bitaro.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(; j < B.size() && use[B[j].first] == True; ++ j);
      |               ~~^~~~~~~~~~
bitaro.cpp:26:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if(i == A.size() && j == B.size()) {
      |            ~~^~~~~~~~~~~
bitaro.cpp:26:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if(i == A.size() && j == B.size()) {
      |                             ~~^~~~~~~~~~~
bitaro.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if(j == B.size() || (i < A.size() && B[j].second < A[i].second)) {
      |            ~~^~~~~~~~~~~
bitaro.cpp:29:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if(j == B.size() || (i < A.size() && B[j].second < A[i].second)) {
      |                              ~~^~~~~~~~~~
bitaro.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < A.size(); ++ i) {
      |                    ~~^~~~~~~~~~
bitaro.cpp: At global scope:
bitaro.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for(; i < calc[T].size() && use[calc[T][i].first] == True; ++ i);
      |                   ~~^~~~~~~~~~~~~~~~
bitaro.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             cout << (i == calc[T].size() ? -1 : calc[T][i].second) << '\n';
      |                      ~~^~~~~~~~~~~~~~~~~

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