Submission #255550

#	Time	Username	Problem	Language	Result	Execution time	Memory
255550		uacoder123	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1951 ms	420984 KiB

bitaro

    #include <bits/stdc++.h>
    using namespace std;
    #define F first
    #define S second
    #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
    #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
    #define all(x) (x).begin(), (x).end()
    #define sz(x) int(x.size())
    #define mp(i,a) make_pair(i,a)
    #define pb(a) push_back(a)
    #define bit(x,b) (x&(1LL<<b))
     
    typedef long long int lli;
    typedef pair <lli,lli> ii;
    typedef pair <lli,ii> iii;
    typedef vector <lli> vi;
    vi al[100001];
    vector<ii> lis[100001];
    int vis[100001],ans[100001];
    int r=255,co=0;
    vector<int> freq[100001];
    int vis2[100001],n;
    void dfs()
    {
      for(int k=1;k<=n;++k)
      {
      lli ma=0;
      for(int i=0;i<al[k].size();++i)
      {
        for(int j=0;j<lis[al[k][i]].size();++j)
        {
          freq[1+lis[al[k][i]][j].F].pb(lis[al[k][i]][j].S);
          ma=max(ma,1+lis[al[k][i]][j].F);
        }
      }
      freq[0].pb(k);
      while(lis[k].size()<r)
      {
        if(freq[ma].size()==0)
          ma-=1;
        if(ma==-1)
          break;
        if(!vis2[freq[ma].back()])
        {
          lis[k].pb(mp(ma,freq[ma].back()));
          vis2[freq[ma].back()]=1;
        }
        freq[ma].pop_back();
      }
      for(int i=0;i<lis[k].size();++i)
        vis2[lis[k][i].S]=0;
      for(int i=0;i<al[k].size();++i)
        for(int j=0;j<lis[al[k][i]].size();++j)
          if(freq[lis[al[k][i]][j].F+1].size()>0)
            freq[lis[al[k][i]][j].F+1].clear();
    freq[0].clear();
  }
    }
    void dfs1(int node)
    {
      for(int k=1;k<=node;++k)
      {
      ans[k]=0;
      for(int i=0;i<al[k].size();++i)
      {
          ans[k]=max(ans[k],1+ans[al[k][i]]);
      }
      if(ans[k]==0&&vis[k]==1)
        ans[k]=-1;
    }
    }
    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int m,q;
      cin>>n>>m>>q;
      for(int i=0;i<m;++i)
      {
        int f,s;
        cin>>f>>s;
        al[s].pb(f);
      }
      dfs();
      vi v;
      for(int i=0;i<q;++i)
      {
        int s,no;
        cin>>s>>no;
        int an=-1;
        for(int j=0;j<no;++j)
          {
            int f;
            cin>>f;
            vis[f]=1;
            v.pb(f);
          }
          if(no<r)
          {
        for(auto j=0;j<lis[s].size();++j)
          {
            if(vis[lis[s][j].S]==0)
            {
              an=lis[s][j].F;
              break;
            }
          }
        }
        if(no>=r)
        {
          dfs1(s);
          an=ans[s];
        }
        for(int j=0;j<v.size();++j)
            vis[v[j]]=0;
          v.clear();
        cout<<an<<'\n';
      }
      return 0;
    }

Compilation message (stderr)

bitaro.cpp: In function 'void dfs()':
bitaro.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<al[k].size();++i)
                   ~^~~~~~~~~~~~~
bitaro.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<lis[al[k][i]].size();++j)
                     ~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(lis[k].size()<r)
             ~~~~~~~~~~~~~^~
bitaro.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<lis[k].size();++i)
                   ~^~~~~~~~~~~~~~
bitaro.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<al[k].size();++i)
                   ~^~~~~~~~~~~~~
bitaro.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<lis[al[k][i]].size();++j)
                     ~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'void dfs1(int)':
bitaro.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<al[k].size();++i)
                   ~^~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:100:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(auto j=0;j<lis[s].size();++j)
                      ~^~~~~~~~~~~~~~
bitaro.cpp:114:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<v.size();++j)
                     ~^~~~~~~~~

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