Submission #486011

#	Time	Username	Problem	Language	Result	Execution time	Memory
486011		danikoynov	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	143 ms	25616 KiB

bitaro

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;
typedef long long ll;
const int maxn = 200010;
int block_sz;

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

int n, m, q, used[maxn], dp[maxn], ins[maxn];
vector < int > g[maxn];
vector < pair < int, int > > d[maxn];

void dfs(int v)
{
    d[v].push_back({0, v});
    for (int i = 0; i < g[v].size(); i ++)
    {
        int u = g[v][i];
        vector < pair < int, int > > k;
        int idx1 = 0, idx2 = 0;
        while((idx1 < d[u].size() || idx2 < d[v].size()) && k.size() < block_sz + 1)
        {
            if (idx1 == d[u].size())
            {
                if (!ins[d[v][idx2].second])
                {
                    k.push_back(d[v][idx2]);
                    ins[d[v][idx2].second] = 1;
                }
                idx2 ++;
            }
            else if (idx2 == d[v].size())
            {
                if (!ins[d[u][idx1].second])
                {
                    k.push_back({d[u][idx1].first + 1, d[u][idx2].second});
                    ins[d[u][idx1].second] = 1;
                }
                idx1 ++;
            }
            else
            {
                if (d[u][idx1].first + 1 > d[v][idx2].first)
                {
                    if (!ins[d[u][idx1].second])
                    {
                        k.push_back({d[u][idx1].first + 1, d[u][idx2].second});
                        ins[d[u][idx1].second] = 1;
                    }
                    idx1 ++;
                }
                else
                {
                    if (!ins[d[v][idx2].second])
                    {
                        k.push_back(d[v][idx2]);
                        ins[d[v][idx2].second] = 1;
                    }
                    idx2 ++;
                }
            }
        }
        for (int j = 0; j < k.size(); j ++)
            ins[k[j].second] = 0;
        d[v] = k;
    }
}

int blocked[maxn];

void solve_dp(int v)
{
    dp[v] = -1;
    used[v] = 1;
    if (!blocked[v])
        dp[v] = 0;
    for (int i = 0; i < g[v].size(); i ++)
    {
        int u = g[v][i];
        if (used[u] == 0)
        solve_dp(u);
        if (dp[u] != -1)
        {
            if (dp[u] + 1 > dp[v])
                dp[v] = dp[u] + 1;
        }
    }
}

void solve()
{
    cin >> n >> m >> q;
    block_sz = sqrt(n);
    for (int i = 1; i <= m; i ++)
    {
        int s, e;
        cin >> s >> e;
        g[e].push_back(s);
    }

    for (int i = 1; i <= n; i ++)
            dfs(i);

    int t, y, c;
    vector < int > sp;
    for (int i = 1; i <= q; i ++)
    {

        cin >> t >> y;
        for (int j = 1; j <= y; j ++)
        {
            cin >> c;
            sp.push_back(c);
            blocked[c] = 1;
        }

        if (y > block_sz)
        {
            solve_dp(t);
            cout << dp[t] << endl;
            memset(used, 0, sizeof(used));
        }
        else
        {
            int idx = 0;
            while(idx < d[t].size() && blocked[d[t][idx].second])
                idx ++;

            if (idx == d[t].size())
                cout << -1 << endl;
            else
                cout << d[t][idx].first << endl;
        }

        for (int j = 0; j < y; j ++)
            blocked[sp[j]] = 0;
            sp.clear();
    }
}

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

Compilation message (stderr)

bitaro.cpp: In function 'void dfs(int)':
bitaro.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < g[v].size(); i ++)
      |                     ~~^~~~~~~~~~~~~
bitaro.cpp:36: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]
   36 |         while((idx1 < d[u].size() || idx2 < d[v].size()) && k.size() < block_sz + 1)
      |                ~~~~~^~~~~~~~~~~~~
bitaro.cpp:36: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]
   36 |         while((idx1 < d[u].size() || idx2 < d[v].size()) && k.size() < block_sz + 1)
      |                                      ~~~~~^~~~~~~~~~~~~
bitaro.cpp:36:70: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |         while((idx1 < d[u].size() || idx2 < d[v].size()) && k.size() < block_sz + 1)
      |                                                             ~~~~~~~~~^~~~~~~~~~~~~~
bitaro.cpp:38: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]
   38 |             if (idx1 == d[u].size())
      |                 ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             else if (idx2 == d[v].size())
      |                      ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:78:27: 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 |         for (int j = 0; j < k.size(); j ++)
      |                         ~~^~~~~~~~~~
bitaro.cpp: In function 'void solve_dp(int)':
bitaro.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < g[v].size(); i ++)
      |                     ~~^~~~~~~~~~~~~
bitaro.cpp: In function 'void solve()':
bitaro.cpp:141:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             while(idx < d[t].size() && blocked[d[t][idx].second])
      |                   ~~~~^~~~~~~~~~~~~
bitaro.cpp:144: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]
  144 |             if (idx == d[t].size())
      |                 ~~~~^~~~~~~~~~~~~~
bitaro.cpp:150:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  150 |         for (int j = 0; j < y; j ++)
      |         ^~~
bitaro.cpp:152:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  152 |             sp.clear();
      |             ^~

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