제출 #212528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
212528		brcode	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2075 ms	18548 KiB

bitaro

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
const int sqrtn = 100;
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;
unordered_map<int,int> m1;
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;
    m1.clear();
    
    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);
        }
        
    }
    a.clear();
    for(auto x = m1.begin();x!=m1.end();x++){
        a.push_back(make_pair(x->second,x->first));
  
    }
   
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());

    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);
        }
        //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

        }

    }
    //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);
            //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;
            }
            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";
            }
        }
        
    }
}

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'void merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >)':
bitaro.cpp:18:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++){
                 ~^~~~~~~~~
bitaro.cpp:29: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:59:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<hold.size();i++){
                 ~^~~~~~~~~~~~

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