Submission #212892

#	Time	Username	Problem	Language	Result	Execution time	Memory
212892		brcode	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1586 ms	126840 KiB

bitaro

#include <iostream>
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int MAXN = 2e5+5;
const int sqrtn = 110;
int w,e;
vector<pair<int,int>> res;
int n,m,q;
bool blocked[MAXN];
int dp[MAXN];
vector<int> v1[MAXN];
vector<int> v1rev[MAXN];
vector<pair<int,int>> temp[MAXN];
vector<int> hold;
int m1[MAXN];
 vector<pair<int,int>> c;
void merge(vector<pair<int,int>> &a,vector<pair<int,int>> b){
    
    c.clear();
    int ind = 0;
    for(int i=0;i<b.size();i++){
        while(ind<a.size() && a[ind].first>=b[i].first+1){
            c.push_back(make_pair(a[ind].first,a[ind].second));
            ind++;
        }
        c.push_back(make_pair(b[i].first+1,b[i].second));
    }
    while(ind<a.size()){
            c.push_back(make_pair(a[ind].first,a[ind].second));
            ind++;
    }
    int cnt = 0;
    for(int i=0;i<c.size();i++){
        //cout<<e<<" "<<w<<" "<<c[i].first<<" "<<c[i].second<<endl;
        if(m1[c[i].second]){
            m1[c[i].second] = 0;
        }
    }
    b.clear();
    for(int i=0;i<c.size() && cnt<sqrtn;i++){
        if(!m1[c[i].second]){
            //if node not seen yet, add it to possible nodes,set it to the distance
            m1[c[i].second] = c[i].first;
            b.push_back(make_pair(c[i].second,0));
            cnt++;
        }else{
            m1[c[i].second] = max(m1[c[i].second],c[i].first);
        }
        
    }
    a.clear();
    for(auto x:b){
        a.push_back(make_pair(m1[x.first],x.first));
  
    }
   
    while(a.size()>sqrtn){
        a.pop_back();
    }
}
int dodp(int t){
    for(int i=1;i<=n;i++){
        blocked[i] = false;
        dp[i] = 0;
    }
    for(int i=0;i<hold.size();i++){
        blocked[hold[i]] = true;
    }
    for(int i=1;i<=n;i++){
        if(blocked[i]){
            dp[i] = -1e9;
        }else{
            dp[i] = 0;
        }
        for(int x:v1rev[i]){
            dp[i] = max(dp[i],dp[x]+1);
        }
        if(i==t){
            return max(-1,dp[t]);
        }
        //cout<<123<<" "<<dp[i]<<endl;
    }
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        v1[u].push_back(v);
        v1rev[v].push_back(u);
        //v1rev -> backwards
    }
    for(int i=1;i<=n;i++){
        
        temp[i].push_back(make_pair(0,i));
        for(int x:v1rev[i]){
          
           //temp[v].push_back(make_pair(1,1));
            
            merge(temp[i],temp[x]);
            //Keep merging temp[i] with nodes which connect to it to find furthest nodes
        
        }
 
        //cout<<temp[i][0].first<<endl;
    }
   // cout<<123<<endl;
    for(int i=1;i<=n;i++){
        m1[i] = -1;
    }
    //cout<<cnt3<<endl;
    //cout<<temp[544].size()<<endl;
    while(q--){
        
        int t,c;
        cin>>t>>c;
      //  cout<<t<<" "<<c<<endl;
        hold.clear();
       // set<int> s1;
        for(int i=1;i<=c;i++){
            int x;
            cin>>x;
            hold.push_back(x);
            m1[x] = q;
            //s1.insert(x);
        }
        //sort(hold.begin(),hold.end());
        if(hold.size()>=sqrtn){
            cout<<dodp(t)<<"\n";
        }else{
            bool ok = false;
            //cout<<t<<" "<<c<<endl;
            if(hold.size() == 0){
                if(temp[t].size()){
                    cout<<temp[t][0].first<<"\n";
                }else{
                    cout<<-1<<"\n";
                }
                continue;
            }
           // sort(hold.begin(),hold.end());
            for(auto x:temp[t]){
               // cout<<t<<" "<<c<<" "<<x.first<<" "<<x.second<<endl;
                
                if(m1[x.second]!=q){
                    cout<<x.first<<"\n";
                    ok = true;
                    break;
                }
            }
            if(!ok){
                cout<<-1<<"\n";
            }
        }
        
    }
}

Compilation message (stderr)

bitaro.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
bitaro.cpp:7:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
bitaro.cpp: In function 'void merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >)':
bitaro.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++){
                 ~^~~~~~~~~
bitaro.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ind<a.size() && a[ind].first>=b[i].first+1){
               ~~~^~~~~~~~~
bitaro.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ind<a.size()){
           ~~~^~~~~~~~~
bitaro.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<c.size();i++){
                 ~^~~~~~~~~
bitaro.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<c.size() && cnt<sqrtn;i++){
                 ~^~~~~~~~~
bitaro.cpp: In function 'int dodp(int)':
bitaro.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<hold.size();i++){
                 ~^~~~~~~~~~~~
bitaro.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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