Submission #212513

#	Time	Username	Problem	Language	Result	Execution time	Memory
212513		brcode	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2081 ms	17912 KiB

bitaro

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
const int sqrtn = 300;
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;
void merge(vector<pair<int,int>> a,vector<pair<int,int>> b){
    
    for(int i=0;i<b.size();i++){
        a.push_back(make_pair(b[i].first+1,b[i].second));
        
    }
    //dist,node
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    int cnt = 0;
    map<int,int> m1;
    for(int i=0;i<a.size() && cnt<=sqrtn;i++){
        
        if(!m1[a[i].second]){
            //if node not seen yet, add it to possible nodes,set it to the distance
            m1[a[i].second] = a[i].first;
            
            cnt++;
        }else{
            m1[a[i].second] = max(m1[a[i].second],a[i].first);
        }
        
    }
    res.clear();
    for(auto x = m1.begin();x!=m1.end();x++){
        res.push_back(make_pair(x->second,x->first));
  
    }
    sort(res.begin(),res.end());
    reverse(res.begin(),res.end());
    while(res.size()>sqrtn){
        res.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);
        }
        //cout<<123<<" "<<dp[i]<<endl;
    }
    return max(-1,dp[t]);
}
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]){
            w=i;
            e=x;
           //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
            temp[i].clear();
            for(auto y:res){
                //cout<<1234<<endl;
                temp[i].push_back(y);
               // cout<<i<<" "<<y.first<<" "<<y.second<<endl;
            }
        }
        for(auto y:temp[i]){
            if(i==11){
             // cout<<i<<" "<<y.second<<" "<<y.first<<endl;
            }
        }
    }
    for(int i=1;i<=n;i++){
        sort(temp[i].begin(),temp[i].end());
        reverse(temp[i].begin(),temp[i].end());
    }
    
    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);
            //s1.insert(x);
        }
        sort(hold.begin(),hold.end());
        if(hold.size()>sqrtn){
            cout<<dodp(t)<<"\n";
        }else{
            bool ok = false;
            //cout<<t<<" "<<c<<endl;
            for(auto x:temp[t]){
               // cout<<t<<" "<<c<<" "<<x.first<<" "<<x.second<<endl;
                if(!binary_search(hold.begin(),hold.end(),x.second)){
                    cout<<x.first<<"\n";
                    ok = true;
                    break;
                }
            }
            if(!ok){
                cout<<-1<<"\n";
            }
        }
        
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'void merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++){
                 ~^~~~~~~~~
bitaro.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size() && cnt<=sqrtn;i++){
                 ~^~~~~~~~~
bitaro.cpp: In function 'int dodp(int)':
bitaro.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<hold.size();i++){
                 ~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:98:18: warning: variable 'y' set but not used [-Wunused-but-set-variable]
         for(auto y:temp[i]){
                  ^

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