Submission #570409

#	Time	Username	Problem	Language	Result	Execution time	Memory
570409		Hanksburger	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1516 ms	420444 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int num=320;
vector<pair<int, int> > vec[100005], tmp;
vector<int> adj[100005], jda[100005];
int dp[100005], exist[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, q, cnt=0;
    cin >> n >> m >> q;
    for (int i=0; i<m; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        jda[v].push_back(u);
    }
    for (int i=1; i<=n; i++)
    {
        vec[i].push_back({0, i});
        for (int j:jda[i])
        {
            int ind=0, jnd=0;
            cnt++;
            for (int k=0; k<num; k++)
            {
                while (ind!=vec[i].size() && exist[vec[i][ind].second]==cnt)
                    ind++;
                while (jnd!=vec[j].size() && exist[vec[j][jnd].second]==cnt)
                    jnd++;
                if (ind==vec[i].size() && jnd==vec[j].size())
                    break;
                if (jnd!=vec[j].size() && vec[j][jnd].first>=vec[i][ind].first)
                {
                    tmp.push_back({vec[j][jnd].first+1, vec[j][jnd].second});
                    exist[vec[j][jnd].second]=cnt;
                    jnd++;
                }
                else
                {
                    tmp.push_back(vec[i][ind]);
                    exist[vec[i][ind].second]=cnt;
                    ind++;
                }
            }
            vec[i].clear();
            for (int k=0; k<tmp.size(); k++)
                vec[i].push_back(tmp[k]);
            tmp.clear();
        }
    }
    for (int i=0; i<q; i++)
    {
        int t, y, ans=-1;
        cin >> t >> y;
        cnt++;
        for (int j=0; j<y; j++)
        {
            int c;
            cin >> c;
            exist[c]=cnt;
        }
        if (y<num)
        {
            bool imp=1;
            for (int j=0; j<vec[t].size(); j++)
            {
                if (exist[vec[t][j].second]!=cnt)
                {
                    cout << vec[t][j].first << '\n';
                    imp=0;
                    break;
                }
            }
            if (imp)
                cout << -1 << '\n';
            continue;
        }
        for (int j=1; j<=n; j++)
            dp[j]=-1e9;
        dp[t]=0;
        if (exist[t]!=cnt)
            ans=0;
        for (int j=t-1; j>=1; j--)
        {
            for (int k:adj[j])
                dp[j]=max(dp[j], dp[k]+1);
            if (exist[j]!=cnt)
                ans=max(ans, dp[j]);
        }
        cout << ans << '\n';
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:30: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]
   30 |                 while (ind!=vec[i].size() && exist[vec[i][ind].second]==cnt)
      |                        ~~~^~~~~~~~~~~~~~~
bitaro.cpp:32: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]
   32 |                 while (jnd!=vec[j].size() && exist[vec[j][jnd].second]==cnt)
      |                        ~~~^~~~~~~~~~~~~~~
bitaro.cpp:34:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                 if (ind==vec[i].size() && jnd==vec[j].size())
      |                     ~~~^~~~~~~~~~~~~~~
bitaro.cpp:34:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                 if (ind==vec[i].size() && jnd==vec[j].size())
      |                                           ~~~^~~~~~~~~~~~~~~
bitaro.cpp:36:24: 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 |                 if (jnd!=vec[j].size() && vec[j][jnd].first>=vec[i][ind].first)
      |                     ~~~^~~~~~~~~~~~~~~
bitaro.cpp:50:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for (int k=0; k<tmp.size(); k++)
      |                           ~^~~~~~~~~~~
bitaro.cpp:69:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int j=0; j<vec[t].size(); j++)
      |                           ~^~~~~~~~~~~~~~

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