Submission #886932

#	Time	Username	Problem	Language	Result	Execution time	Memory
886932		imarn	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1282 ms	414336 KiB

bitaro

#include<bits/stdc++.h>
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second
#define vi vector<int>
#define vpii vector<pii>
#define ll long long
using namespace std;
const int N=1e5+5;
vector<int>g[N];
vector<pii>lg[N];
const int sq=317;
bool vis[N]{0};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;g[v].pb(u);
    }
    for(int i=1;i<=n;i++){
        lg[i].pb({0,i});
        for(auto v:g[i]){
            int l=0,r=0;
            vector<pii>tmp;
            while(l<lg[i].size()&&r<lg[v].size()&&sz(tmp)<sq){
                if(lg[i][l].f<=lg[v][r].f+1){
                    tmp.pb({lg[v][r].f+1,lg[v][r].s});vis[lg[v][r].s]=1;
                    while(r<lg[v].size()&&vis[lg[v][r].s])r++;
                    while(l<lg[i].size()&&vis[lg[i][l].s])l++;
                }
                else {
                    tmp.pb({lg[i][l].f,lg[i][l].s}),vis[lg[i][l].s]=1;
                    while(l<lg[i].size()&&vis[lg[i][l].s])l++;
                    while(r<lg[v].size()&&vis[lg[v][r].s])r++;
                }
            }while(l<lg[i].size()&&sz(tmp)<sq){
                tmp.pb({lg[i][l].f,lg[i][l].s}),vis[lg[i][l].s]=1;
                while(l<lg[i].size()&&vis[lg[i][l].s])l++;
                while(r<lg[v].size()&&vis[lg[v][r].s])r++;
            }
            while(r<lg[v].size()&&sz(tmp)<sq){
                tmp.pb({lg[v][r].f+1,lg[v][r].s});vis[lg[v][r].s]=1;
                while(r<lg[v].size()&&vis[lg[v][r].s])r++;
                while(l<lg[i].size()&&vis[lg[i][l].s])l++;
            }for(auto it : tmp)vis[it.s]=0;
            swap(tmp,lg[i]);
        }
    }memset(vis,0,sizeof vis);
    while(q--){
        int y,t;cin>>t>>y;
        int ans=-1;int a[y+1];
        for(int i=1;i<=y;i++)cin>>a[i],vis[a[i]]=1;
        if(y>sq-5){
            int dp[t+1]={0};
            for(int i=1;i<=t;i++)if(vis[i])dp[i]=-1e9;
            for(int i=1;i<=t;i++){
                for(auto v : g[i])dp[i] = max(dp[i],dp[v]+1);
            }cout<<(dp[t]<0?-1:dp[t])<<"\n";
        }else {
            for(auto it : lg[t])if(!vis[it.s])ans=max(ans,it.f);
            cout<<ans<<'\n';
        }for(int i=1;i<=y;i++)vis[a[i]]=0;
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while(l<lg[i].size()&&r<lg[v].size()&&sz(tmp)<sq){
      |                   ~^~~~~~~~~~~~~
bitaro.cpp:30:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while(l<lg[i].size()&&r<lg[v].size()&&sz(tmp)<sq){
      |                                   ~^~~~~~~~~~~~~
bitaro.cpp:33:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                     while(r<lg[v].size()&&vis[lg[v][r].s])r++;
      |                           ~^~~~~~~~~~~~~
bitaro.cpp:34:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                     while(l<lg[i].size()&&vis[lg[i][l].s])l++;
      |                           ~^~~~~~~~~~~~~
bitaro.cpp:38:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                     while(l<lg[i].size()&&vis[lg[i][l].s])l++;
      |                           ~^~~~~~~~~~~~~
bitaro.cpp:39:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |                     while(r<lg[v].size()&&vis[lg[v][r].s])r++;
      |                           ~^~~~~~~~~~~~~
bitaro.cpp:41: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]
   41 |             }while(l<lg[i].size()&&sz(tmp)<sq){
      |                    ~^~~~~~~~~~~~~
bitaro.cpp:43:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                 while(l<lg[i].size()&&vis[lg[i][l].s])l++;
      |                       ~^~~~~~~~~~~~~
bitaro.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |                 while(r<lg[v].size()&&vis[lg[v][r].s])r++;
      |                       ~^~~~~~~~~~~~~
bitaro.cpp:46:20: 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 |             while(r<lg[v].size()&&sz(tmp)<sq){
      |                   ~^~~~~~~~~~~~~
bitaro.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 while(r<lg[v].size()&&vis[lg[v][r].s])r++;
      |                       ~^~~~~~~~~~~~~
bitaro.cpp:49:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                 while(l<lg[i].size()&&vis[lg[i][l].s])l++;
      |                       ~^~~~~~~~~~~~~

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