Submission #886924

#	Time	Username	Problem	Language	Result	Execution time	Memory
886924		imarn	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	4 ms	8028 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],gg[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);gg[u].pb(v);
    }
    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++;
                }
                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(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()&&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++;
            }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){
            int dp[n+1]={0};
            for(int i=1;i<=n;i++)dp[i]=-1;
            if(!vis[t])dp[t]=0,ans=0;
            for(int i=t-1;i>=1;i--){
                for(auto v:gg[i])if(dp[v]!=-1)dp[i]=max(dp[i],dp[v]+1);
                if(!vis[i])ans=max(ans,dp[i]);
            }cout<<ans<<'\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:37: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]
   37 |                     while(l<lg[i].size()&&vis[lg[i][l].s])l++;
      |                           ~^~~~~~~~~~~~~
bitaro.cpp:39: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]
   39 |             }while(l<lg[i].size()&&sz(tmp)<sq){
      |                    ~^~~~~~~~~~~~~
bitaro.cpp:41: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]
   41 |                 while(l<lg[i].size()&&vis[lg[i][l].s])l++;
      |                       ~^~~~~~~~~~~~~
bitaro.cpp:43: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]
   43 |             while(r<lg[v].size()&&sz(tmp)<sq){
      |                   ~^~~~~~~~~~~~~
bitaro.cpp:45: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]
   45 |                 while(r<lg[v].size()&&vis[lg[v][r].s])r++;
      |                       ~^~~~~~~~~~~~~

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