Submission #886906

#	Time	Username	Problem	Language	Result	Execution time	Memory
886906		imarn	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	995 ms	411304 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];
int sq;
int vis[N];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,q;cin>>n>>m>>q;sq=sqrt(n);
    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});vis[i]=-1;
        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}),r++;
                else tmp.pb({lg[i][l].f,lg[i][l].s}),l++;
            }while(l<lg[i].size()&&sz(tmp)<sq)tmp.pb({lg[i][l].f,lg[i][l].s}),l++;
            while(r<lg[v].size()&&sz(tmp)<sq)tmp.pb({lg[v][r].f+1,lg[v][r].s}),r++;
            swap(tmp,lg[i]);
        }
    }
    while(q--){
        int y,t;cin>>t>>y;
        int ans=-1;
        for(int i=1,u;i<=y;i++)cin>>u,vis[u]=q;
        if(y>=sq){
            int dp[t+1]={0};
            for(int i=1;i<=t;i++)if(vis[i]==q)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]!=q)ans=max(ans,it.f);
            cout<<ans<<'\n';
        }
    }
}

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: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]
   33 |             }while(l<lg[i].size()&&sz(tmp)<sq)tmp.pb({lg[i][l].f,lg[i][l].s}),l++;
      |                    ~^~~~~~~~~~~~~
bitaro.cpp:34: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]
   34 |             while(r<lg[v].size()&&sz(tmp)<sq)tmp.pb({lg[v][r].f+1,lg[v][r].s}),r++;
      |                   ~^~~~~~~~~~~~~

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