제출 #212515

#제출 시각아이디문제언어결과실행 시간메모리
212515brcodeBitaro’s Party (JOI18_bitaro)C++14
14 / 100
191 ms27512 KiB
#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;
    unordered_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);
        }
        
    }
    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()){
        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


        }

    }

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

컴파일 시 표준 에러 (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:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<hold.size();i++){
                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...