Submission #336585

#	Time	Username	Problem	Language	Result	Execution time	Memory
336585		mehrdad_sohrabi	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1444 ms	321900 KiB

bitaro

#include <bits/stdc++.h>
typedef int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=1e5+100,sq=400;
pii mx[N][sq];
vector <int> g[N];
ll vis[N];
ll dp[N];
int32_t main(){
    sync;
    ll n,m,q;
    cin >> n >> m >> q;
    for (int i=0;i<m;i++){
        ll u,v;
        cin >> v >> u;
        g[u].pb(v);
    }
    for (int i=1;i<=n;i++){
        for (int j=0;j<sq;j++){
            mx[i][j]={-1,-1};
        }
    }
    ll cntt=1;
    for (int i=1;i<=n;i++){
        cntt++;
        vector <int> cnt;
        for (int j=0;j<g[i].size();j++){
            cnt.pb(0);
        }
        if (cnt.size()==0) {
            for (int j=0;j<sq;j++){
                mx[i][j]={0,i};
            }
            continue;
        }
        for (int j=0;j<sq;j++){
            pii p={0,i};
            ll id=0;
            for (int k=0;k<g[i].size();k++){
                ll u=g[i][k];
                ll z=cnt[k];
                if (z<sq && mx[u][z].F>=p.F) p=mx[u][z],id=k,p.F++;
            }
            vis[p.S]=cntt;
          //  cout << p.F << " rfh " << p.S << endl;
      //      cnt[id]++;
            for (int k=0;k<g[i].size();k++){
                ll u=g[i][k];\
                ll z=cnt[k];
                while (cnt[k]<sq && mx[u][cnt[k]].S!=-1 && vis[mx[u][cnt[k]].S]==cntt) cnt[k]++;
            }
            mx[i][j]=p;
           // if (p.F==0) break;
        }
    }
  //  cout << 1 << endl;
    //return 0;
    while(q--){
        cntt++;
        ll w,t;
        cin >> w >> t;
        for (int i=0;i<t;i++){
            ll x;
            cin >> x;
            vis[x]=cntt;
        }
        ll ans=-1;
        for (int i=0;i<sq;i++){
            if (mx[w][i].S==-1) break;
            if (vis[mx[w][i].S]!=cntt){
                ans=mx[w][i].F;
                break;
            }
        }
        if (ans>-1){
            cout << ans << endl;
            continue;
        }
        if ( mx[w][sq-1].S==w || mx[w][sq-1].S==-1) {
            cout << -1 << endl;
            continue;
        }
        for (int i=1;i<=w;i++){
            if (vis[i]==cntt) dp[i]=-1;
            else dp[i]=0;
            for (auto u : g[i]){
                if (dp[u]==-1) continue;
                dp[i]=max(dp[i],dp[u]+1);
            }
        }
        cout << dp[w] << endl;
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int j=0;j<g[i].size();j++){
      |                      ~^~~~~~~~~~~~
bitaro.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for (int k=0;k<g[i].size();k++){
      |                          ~^~~~~~~~~~~~
bitaro.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for (int k=0;k<g[i].size();k++){
      |                          ~^~~~~~~~~~~~
bitaro.cpp:59:20: warning: unused variable 'z' [-Wunused-variable]
   59 |                 ll z=cnt[k];
      |                    ^
bitaro.cpp:48:16: warning: variable 'id' set but not used [-Wunused-but-set-variable]
   48 |             ll id=0;
      |                ^~

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