제출 #1103461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103461		hoangnoobpro	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2086 ms	412480 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define nmax 100007
#define fi first
#define se second
#define ll int
ll t=1,n,m=0,i=0,j=0,d=0,x=0,k=0,y=0,z,a[nmax],b[nmax],h[nmax],f[nmax],deg[nmax];
vector<ll>v[nmax];
vector<pair<ll,ll>>luu[nmax],tam;
queue<ll>dq;
bool cmp(pair<ll,ll>a,pair<ll,ll>b)
{
    return a.fi>b.fi;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>t;
    for(i=1;i<=m;++i)
    {
        cin>>x>>y;
        v[x].push_back(y);
        deg[y]++;
    }
    for(i=1;i<=n;++i)
    {
        if(!deg[i])dq.push(i);
//        luu[i].push_back({0,i});
    }
    z=sqrt(n);
    while(dq.size()>0)
    {
        x=dq.front();
        dq.pop();
        luu[x].push_back({0,x});
        for(i=0;i<v[x].size();++i)
        {
            y=v[x][i];
            tam=luu[y];
            luu[y].clear();
            d=0;
            j=k=0;
            while(d<z)
            {
                if(j==luu[x].size()||k==tam.size())break;
                d++;
                if(luu[x][j].fi>=tam[k].fi)
                {
//                    if(y==4)cout<<luu[x][j].fi<<" "<<luu[x][j].se<<" ("<<x<<")"<<",\n";
                    luu[y].push_back({luu[x][j].fi+1,luu[x][j].se});
                    j++;
                    continue;
                }
                luu[y].push_back({tam[k].fi+1,tam[k].se});
                k++;
            }
            while(d<z&&j<luu[x].size())
            {
                luu[y].push_back({luu[x][j].fi+1,luu[x][j].se});
                j++;
            }
            while(d<z&&k<tam.size())
            {
                luu[y].push_back({tam[k].fi+1,tam[k].se});
                k++;
            }
            tam.clear();
            ///
            sort(luu[y].begin(),luu[y].end(),cmp);
            deg[y]--;
            if(deg[y]==0)
            {
                dq.push(y);
            }
        }
    }
    x=sqrt(n);
    while(t--)
    {
        cin>>y>>z;
        for(i=1;i<=z;++i)
        {
            cin>>b[i];
            f[b[i]]=1;
        }
        ///
//        if(z<x)
//        {
//           d=-1;
//           for(i=0;i<luu[y].size();++i)
//           {
//               if(!f[luu[y][i].se])d=max(d,luu[y][i].fi);
//           }
//           if(!f[y]&&d<0)d=0;
//           cout<<d<<"\n";
//           for(i=1;i<=z;++i)f[b[i]]=0;
//        }
//        continue;
        ///
        d=-1;
        for(i=1;i<=y;++i)
            if(!f[i]||h[i])
        {
            for(j=0;j<v[i].size();++j)
            {
                h[v[i][j]]=max(h[v[i][j]],h[i]+1);
            }
        }
        if(h[y])d=h[y];
        if(!f[y]&&d<0)d=0;
        cout<<d<<"\n";
        for(i=1;i<=n;++i)f[i]=h[i]=0;
    }

//    cout<<"\n\n\n";
//    for(i=1;i<=n;++i)
//    {
//        cout<<luu[i].size()<<": ";
//        for(j=0;j<luu[i].size();++j)cout<<luu[i][j].fi<<" "<<luu[i][j].se<<", ";
//        cout<<"\n";
//    }
}

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(i=0;i<v[x].size();++i)
      |                 ~^~~~~~~~~~~~
bitaro.cpp:46: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]
   46 |                 if(j==luu[x].size()||k==tam.size())break;
      |                    ~^~~~~~~~~~~~~~~
bitaro.cpp:46:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |                 if(j==luu[x].size()||k==tam.size())break;
      |                                      ~^~~~~~~~~~~~
bitaro.cpp:58:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             while(d<z&&j<luu[x].size())
      |                        ~^~~~~~~~~~~~~~
bitaro.cpp:63:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             while(d<z&&k<tam.size())
      |                        ~^~~~~~~~~~~
bitaro.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for(j=0;j<v[i].size();++j)
      |                     ~^~~~~~~~~~~~

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