Submission #991768

#	Time	Username	Problem	Language	Result	Execution time	Memory
991768		danikoynov	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	692 ms	258268 KiB

bitaro

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10;
int block_size = sqrt(maxn) + 10;

int n, m, q, sp[maxn], dp[maxn];
vector < int > adj[maxn];
void input()
{
    cin >> n >> m >> q;
    block_size = sqrt(n) + 1;
    for (int i = 1; i <= m; i ++)
    {
        int s, e;
        cin >> s >> e;
        adj[e].push_back(s);
    }
}

void compute()
{
    for (int i = 1; i <= n; i ++)
    {
        dp[i] = -1e9;
        if (!sp[i])
            dp[i] = 0;

        for (int u : adj[i])
            dp[i] = max(dp[i], dp[u] + 1);
    }
}

vector < pair < int, int > > fp[maxn];
void precompute()
{
    for (int v = 1; v <= n; v ++)
    {
        fp[v].push_back({0, v});
        for (int u : adj[v])
        {
            vector < pair < int, int > > res;
            int pv = 0, pu = 0;
            while(pv < fp[v].size() && pu < fp[u].size() && res.size() < block_size)
            {
                if (fp[v][pv].first > fp[u][pu].first + 1)
                    res.push_back(fp[v][pv ++]);
                else
                {
                    res.push_back({fp[u][pu].first + 1, fp[u][pu].second});
                    pu ++;
                }
            }

            while(pv < fp[v].size() && res.size() < block_size)
                res.push_back(fp[v][pv ++]);

            while(pu < fp[u].size() && res.size() < block_size)
            {
                res.push_back({fp[u][pu].first + 1, fp[u][pu].second});
                pu ++;
            }

            fp[v] = res;
        }


    }
}
void answer_queries()
{
    for (int i = 1; i <= q; i ++)
    {
        int x, t;
        cin >> t >> x;
        vector < int > spec;
        for (int j = 1; j <= x; j ++)
        {
            int y;
            cin >> y;
            spec.push_back(y);
            sp[y] = 1;
        }

        if (x >= block_size)
        {
            compute();
            if (dp[t] < 0)
                cout << -1 << endl;
            else
                cout << dp[t] << endl;
        }
        else
        {
            int pv = 0;
            while(pv < fp[t].size() && sp[fp[t][pv].second] == 1)
                pv ++;
            if (pv == fp[t].size())
                cout << -1 << endl;
            else
                cout << fp[t][pv].first << endl;
        }

        for (int v : spec)
            sp[v] = 0;
    }
}
void solve()
{
    input();
    precompute();
    answer_queries();
}

int main()
{
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void precompute()':
bitaro.cpp:54: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]
   54 |             while(pv < fp[v].size() && pu < fp[u].size() && res.size() < block_size)
      |                   ~~~^~~~~~~~~~~~~~
bitaro.cpp:54:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while(pv < fp[v].size() && pu < fp[u].size() && res.size() < block_size)
      |                                        ~~~^~~~~~~~~~~~~~
bitaro.cpp:54:72: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |             while(pv < fp[v].size() && pu < fp[u].size() && res.size() < block_size)
      |                                                             ~~~~~~~~~~~^~~~~~~~~~~~
bitaro.cpp:65: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]
   65 |             while(pv < fp[v].size() && res.size() < block_size)
      |                   ~~~^~~~~~~~~~~~~~
bitaro.cpp:65:51: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |             while(pv < fp[v].size() && res.size() < block_size)
      |                                        ~~~~~~~~~~~^~~~~~~~~~~~
bitaro.cpp:68: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]
   68 |             while(pu < fp[u].size() && res.size() < block_size)
      |                   ~~~^~~~~~~~~~~~~~
bitaro.cpp:68:51: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |             while(pu < fp[u].size() && res.size() < block_size)
      |                                        ~~~~~~~~~~~^~~~~~~~~~~~
bitaro.cpp: In function 'void answer_queries()':
bitaro.cpp:106: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]
  106 |             while(pv < fp[t].size() && sp[fp[t][pv].second] == 1)
      |                   ~~~^~~~~~~~~~~~~~
bitaro.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             if (pv == fp[t].size())
      |                 ~~~^~~~~~~~~~~~~~~

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