Submission #991769

#	Time	Username	Problem	Language	Result	Execution time	Memory
991769		danikoynov	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1050 ms	261680 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];
int tk[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)
                {
                    tk[fp[v][pv].second] = 1;
                    res.push_back(fp[v][pv ++]);
                }
                else
                {
                    tk[fp[u][pu].second] = 1;
                    res.push_back({fp[u][pu].first + 1, fp[u][pu].second});
                    pu ++;
                }

                while(pv < fp[v].size() && tk[fp[v][pv].second])
                    pv ++;
                while(pu < fp[u].size() && tk[fp[u][pu].second])
                    pu ++;

            }

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

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

            fp[v] = res;
            for (pair < int, int > cur : res)
                tk[cur.second] = 0;
        }


    }
}
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;
}

/**


12 17 1
1 2
2 3
3 4
1 5
2 6
3 7
4 8
5 6
6 7
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
11 3 1 3 5
*/

Compilation message (stderr)

bitaro.cpp: In function 'void precompute()':
bitaro.cpp:57: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]
   57 |             while(pv < fp[v].size() && pu < fp[u].size() && res.size() < block_size)
      |                   ~~~^~~~~~~~~~~~~~
bitaro.cpp:57: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]
   57 |             while(pv < fp[v].size() && pu < fp[u].size() && res.size() < block_size)
      |                                        ~~~^~~~~~~~~~~~~~
bitaro.cpp:57: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]
   57 |             while(pv < fp[v].size() && pu < fp[u].size() && res.size() < block_size)
      |                                                             ~~~~~~~~~~~^~~~~~~~~~~~
bitaro.cpp:71: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]
   71 |                 while(pv < fp[v].size() && tk[fp[v][pv].second])
      |                       ~~~^~~~~~~~~~~~~~
bitaro.cpp:73: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]
   73 |                 while(pu < fp[u].size() && tk[fp[u][pu].second])
      |                       ~~~^~~~~~~~~~~~~~
bitaro.cpp:78: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]
   78 |             while(pv < fp[v].size() && res.size() < block_size)
      |                   ~~~^~~~~~~~~~~~~~
bitaro.cpp:78: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]
   78 |             while(pv < fp[v].size() && res.size() < block_size)
      |                                        ~~~~~~~~~~~^~~~~~~~~~~~
bitaro.cpp:81: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]
   81 |                 while(pv < fp[v].size() && tk[fp[v][pv].second])
      |                       ~~~^~~~~~~~~~~~~~
bitaro.cpp:85: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]
   85 |             while(pu < fp[u].size() && res.size() < block_size)
      |                   ~~~^~~~~~~~~~~~~~
bitaro.cpp:85: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]
   85 |             while(pu < fp[u].size() && res.size() < block_size)
      |                                        ~~~~~~~~~~~^~~~~~~~~~~~
bitaro.cpp:89: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]
   89 |                 while(pu < fp[u].size() && tk[fp[u][pu].second])
      |                       ~~~^~~~~~~~~~~~~~
bitaro.cpp: In function 'void answer_queries()':
bitaro.cpp:127: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]
  127 |             while(pv < fp[t].size() && sp[fp[t][pv].second] == 1)
      |                   ~~~^~~~~~~~~~~~~~
bitaro.cpp:129: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]
  129 |             if (pv == fp[t].size())
      |                 ~~~^~~~~~~~~~~~~~~

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