Submission #769210

#	Time	Username	Problem	Language	Result	Execution time	Memory
769210		LucaIlie	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2067 ms	19732 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

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

struct sol {
    int u, d;
};

const int MAX_N = 1e5 + 1;
const int MAX_Q = 1e5;
const int INF = 1e9;
bool blocat[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 = 0;//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 < tmax + 1 && i < sols[u].size() + sols[v].size(); i++ ) {
                if ( iu == sols[u].size() || sols[v][iv].d > sols[u][iu].d )
                    aux.push_back( sols[v][iv++] );
                else
                    aux.push_back( sols[u][iu++] );
            }
            sols[u] = aux;
        }
        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( 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:69:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sol>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for ( int i = 0; i < tmax + 1 && i < sols[u].size() + sols[v].size(); i++ ) {
      |                                              ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:70:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sol>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 if ( iu == sols[u].size() || sols[v][iv].d > sols[u][iu].d )
      |                      ~~~^~~~~~~~~~~~~~~~~

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