제출 #255528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255528		uacoder123	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	9 ms	9088 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],vis1[100001],ans[100001];
    int r=50,co=0;
    vector<int> freq[100001];
    int vis2[100001];
    void dfs(int node)
    {
      vis1[node]=1;
      lli ma=0,mi=100000001;
      for(int i=0;i<al[node].size();++i)
      {
        if(!vis1[al[node][i]])
          dfs(al[node][i]);
        for(int j=0;j<lis[al[node][i]].size();++j)
        {
          freq[1+lis[al[node][i]][j].F].pb(lis[al[node][i]][j].S);
          ma=max(ma,1+lis[al[node][i]][0].F);
        }
      }
      while(lis[node].size()<r)
      {
        if(freq[ma].size()==0)
          ma-=1;
        if(ma==-1||freq[ma].size()==0)
          break;
        if(!vis2[freq[ma].back()])
        {
          lis[node].pb(mp(ma,freq[ma].back()));
          vis2[freq[ma].back()]=1;
        }
        freq[ma].pop_back();
      }
      for(int i=0;i<lis[node].size();++i)
        vis2[lis[node][i].S]=0;
      for(int i=0;i<al[node].size();++i)
        for(int j=0;j<lis[al[node][i]].size();++i)
          if(freq[lis[al[node][i]][j].F+1].size()>0)
            freq[lis[al[node][i]][j].F+1].clear();
          if(lis[node].size()<r)
            lis[node].pb(mp(0,node));
    }
    void dfs1(int node)
    {
      ans[node]=0;
      vis1[node]=1;
      for(int i=0;i<al[node].size();++i)
      {
        if(vis1[al[node][i]]==0)
        {
          dfs1(al[node][i]);
        }
          ans[node]=max(ans[node],1+ans[al[node][i]]);
      }
      if(ans[node]==0&&vis[node]==1)
        ans[node]=-1;
    }
    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int n,m,q;
      cin>>n>>m>>q;
      for(int i=0;i<m;++i)
      {
        int f,s;
        cin>>f>>s;
        al[s].pb(f);
      }
      for(int i=n;i>0;--i)
        if(vis1[i]==0)
          dfs(i);
      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);
          }
        for(auto j=0;j<lis[s].size();++j)
          {
            if(vis[lis[s][j].S]==0)
            {
              an=lis[s][j].F;
              break;
            }
          }
        if(an==-1&&no>=r)
        {
          memset(vis1,0,sizeof(vis1));
          dfs1(s);
          an=ans[s];
        }
        for(int j=0;j<v.size();++j)
            vis[v[j]]=0;
          v.clear();
        cout<<an<<'\n';
      }
      return 0;
    }

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'void dfs(int)':
bitaro.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<al[node].size();++i)
                   ~^~~~~~~~~~~~~~~~
bitaro.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<lis[al[node][i]].size();++j)
                     ~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:37:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(lis[node].size()<r)
             ~~~~~~~~~~~~~~~~^~
bitaro.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<lis[node].size();++i)
                   ~^~~~~~~~~~~~~~~~~
bitaro.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<al[node].size();++i)
                   ~^~~~~~~~~~~~~~~~
bitaro.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<lis[al[node][i]].size();++i)
                     ~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:53:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(int j=0;j<lis[al[node][i]].size();++i)
         ^~~
bitaro.cpp:56:11: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
           if(lis[node].size()<r)
           ^~
bitaro.cpp:56:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           if(lis[node].size()<r)
              ~~~~~~~~~~~~~~~~^~
bitaro.cpp:26:16: warning: unused variable 'mi' [-Wunused-variable]
       lli ma=0,mi=100000001;
                ^~
bitaro.cpp: In function 'void dfs1(int)':
bitaro.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<al[node].size();++i)
                   ~^~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:102:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(auto j=0;j<lis[s].size();++j)
                      ~^~~~~~~~~~~~~~
bitaro.cpp:116:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<v.size();++j)
                     ~^~~~~~~~~

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