Submission #774618

#	Time	Username	Problem	Language	Result	Execution time	Memory
774618		DobromirAngelov	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1081 ms	249120 KiB

bitaro

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
using namespace std;

const int MAXN=1e5+5;
const int B=300;

int n,m,q;
pair<int,int> maxd[MAXN][B+5];
vector<int> adj[MAXN];
int dp[MAXN];
int c[MAXN];
bool used[MAXN];

int calc_dp(int v)
{
    memset(dp,-1,sizeof(dp));
    dp[v]=0;
    for(int i=v-1;i>=1;i--)
    {
        for(int j=0;j<adj[i].size();j++)
        {
            if(dp[adj[i][j]]==-1) continue;
            dp[i]=max(dp[i], dp[adj[i][j]]+1);
        }
    }
    int ans=-1;
    for(int i=v;i>=1;i--)
    {
        if(!used[i]) ans=max(ans, dp[i]);
    }
    return ans;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n>>m>>q;
for(int i=0;i<m;i++)
{
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
}

for(int i=0;i<=n;i++)
{
    for(int j=1;j<B;j++) maxd[i][j].fi=-1;
}
for(int i=0;i<=n;i++) maxd[i][0].fi=0, maxd[i][0].se=i;

for(int v=1;v<=n;v++)
{
    for(int j=0;j<adj[v].size();j++)
    {
        int to=adj[v][j];
        int ptr1=0;
        int ptr2=0;
        vector<pair<int,int> > tmp;
        for(;;)
        {
            if(tmp.size()>=B) break;
            pair<int,int> cur={0,0};
            if(maxd[v][ptr1].fi!=-1 && maxd[v][ptr1].fi+1>maxd[to][ptr2].fi)
            {
                cur={maxd[v][ptr1].fi+1, maxd[v][ptr1++].se};
            }
            else if(maxd[to][ptr2].fi!=-1)
            {
                cur={maxd[to][ptr2].fi, maxd[to][ptr2++].se};
            }
            else break;

            if(!used[cur.se])
            {
                tmp.push_back(cur);
                used[cur.se]=1;
            }
        }
        for(int i=0;i<tmp.size();i++) maxd[to][i]=tmp[i];
        for(int i=0;i<tmp.size();i++) used[tmp[i].se]=0;
    }
}

for(int i=0;i<q;i++)
{
    int v,br;
    cin>>v>>br;
    for(int j=0;j<br;j++)
    {
        cin>>c[j];
        used[c[j]]=1;
    }

    if(br<B)
    {
        bool fl=0;
        for(int j=0;j<B;j++)
        {
            if(maxd[v][j].fi<0) break;
            if(!used[maxd[v][j].se])
            {
                cout<<maxd[v][j].fi<<endl;
                fl=1;
                break;
            }
        }
        if(!fl) cout<<-1<<endl;
    }

    else
    {
        int ans=calc_dp(v);
        cout<<ans<<endl;
    }

    for(int j=0;j<br;j++) used[c[j]]=0;
}

return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int calc_dp(int)':
bitaro.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int j=0;j<adj[i].size();j++)
      |                     ~^~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int j=0;j<adj[v].size();j++)
      |                 ~^~~~~~~~~~~~~~
bitaro.cpp:71:54: warning: operation on 'ptr1' may be undefined [-Wsequence-point]
   71 |                 cur={maxd[v][ptr1].fi+1, maxd[v][ptr1++].se};
      |                                                  ~~~~^~
bitaro.cpp:71:54: warning: operation on 'ptr1' may be undefined [-Wsequence-point]
bitaro.cpp:75:54: warning: operation on 'ptr2' may be undefined [-Wsequence-point]
   75 |                 cur={maxd[to][ptr2].fi, maxd[to][ptr2++].se};
      |                                                  ~~~~^~
bitaro.cpp:75:54: warning: operation on 'ptr2' may be undefined [-Wsequence-point]
bitaro.cpp:85: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]
   85 |         for(int i=0;i<tmp.size();i++) maxd[to][i]=tmp[i];
      |                     ~^~~~~~~~~~~
bitaro.cpp:86: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]
   86 |         for(int i=0;i<tmp.size();i++) used[tmp[i].se]=0;
      |                     ~^~~~~~~~~~~

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