Submission #769227

#	Time	Username	Problem	Language	Result	Execution time	Memory
769227		LucaIlie	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1418 ms	423012 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

struct query {
    int q, u;
    vector<int> b;
};

struct sol {
    int u, d;

    sol operator + ( const int &x ) const {
        return { u, d + x };
    }
};

const int MAX_N = 1e5 + 1;
const int MAX_Q = 1e5;
const int INF = 1e9;
bool blocat[MAX_N], used[MAX_N];
int dp[MAX_N], ans[MAX_Q];
vector<int> edges[MAX_N];
vector<query> queryMari;
vector<query> queryMici[MAX_N];
vector<sol> sols[MAX_N];

int main() {
    int n, m, q;

    cin >> n >> m >> q;
    for ( int i = 0; i < m; i++ ) {
        int u, v;
        cin >> u >> v;
        edges[v].push_back( u );
    }

    int tmax = floor( sqrt( n ) );
    for ( int i = 0; i < q; i++ ) {
        int u, t;
        vector<int> b;
        cin >> u >> t;
        for ( int j = 0; j < t; j++ ) {
            int v;
            cin >> v;
            b.push_back( v );
        }
        if ( t > tmax )
            queryMari.push_back( { i, u, b } );
        else
            queryMici[u].push_back( { i, u, b } );
    }

    for ( query q: queryMari ) {
        for ( int u = 1; u <= n; u++ )
            dp[u] = 0;
        for ( int u: q.b )
            dp[u] = -INF;

        for ( int u = 1; u <= q.u; u++ ) {
            for ( int v: edges[u] )
                dp[u] = max( dp[u], dp[v] + 1 );
        }

        ans[q.q] = (dp[q.u] < 0 ? -1: dp[q.u]);
    }

    for ( int u = 1; u <= n; u++ ) {
        sols[u].push_back( { u, 0 } );
        for ( int v: edges[u] ) {
            vector<sol> aux;
            int iu = 0, iv = 0;
            for ( int i = 0; i < sols[u].size() + sols[v].size(); i++ ) {
                if ( iu == sols[u].size() || (iv < sols[v].size() && sols[v][iv].d + 1 > sols[u][iu].d) )
                    aux.push_back( sols[v][iv++] + 1 );
                else
                    aux.push_back( sols[u][iu++] );
            }
            sols[u].clear();
            for ( sol s: aux ) {
                if ( !used[s.u] && sols[u].size() < tmax + 1 ) {
                    used[s.u] = true;
                    sols[u].push_back( s );
                }
            }
            for ( sol s: aux )
                used[s.u] = false;
        }

        for ( query q: queryMici[u] ) {
            for ( int v: q.b )
                blocat[v] = true;

            ans[q.q] = -1;
            for ( sol s: sols[u] ) {
                if ( !blocat[s.u] )
                    ans[q.q] = max( ans[q.q], s.d );
            }

            for ( int v: q.b )
                blocat[v] = false;
        }
    }

    for ( int i = 0; i < q; i++ )
        cout << ans[i] << "\n";

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:73:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sol>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for ( int i = 0; i < sols[u].size() + sols[v].size(); i++ ) {
      |                              ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:74:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sol>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 if ( iu == sols[u].size() || (iv < sols[v].size() && sols[v][iv].d + 1 > sols[u][iu].d) )
      |                      ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:74:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sol>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 if ( iu == sols[u].size() || (iv < sols[v].size() && sols[v][iv].d + 1 > sols[u][iu].d) )
      |                                               ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:81:51: warning: comparison of integer expressions of different signedness: 'std::vector<sol>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |                 if ( !used[s.u] && sols[u].size() < tmax + 1 ) {
      |                                    ~~~~~~~~~~~~~~~^~~~~~~~~~

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