제출 #130213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
130213		doowey	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2061 ms	111096 KiB

bitaro

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 9;
const int K = 125;

const int inf = (int)1e8;

vector<pii> best[N];
vector<int> T[N];
bool use[N];

int dp[N];

bool ban[N];

vector<pii> unite(vector<pii> a, vector<pii> b){
    vector<pii> res;
    int i = 0, j = 0;
    while(i < a.size() && j < b.size() && res.size() < K){
        if(use[a[i].se]){
            i ++ ;
            continue;
        }
        if(use[b[j].se]){
            j ++ ;
            continue;
        }
        if(a[i].fi > b[j].fi + 1){
            res.push_back(mp(a[i].fi, a[i].se));
            use[a[i].se] = true;
            i ++ ;
        }
        else{
            res.push_back(mp(b[j].fi + 1, b[j].se));
            use[b[j].se] = true;
            j ++ ;
        }
    }
    while(i < a.size() && res.size() < K){
        if(!use[a[i].se]){
            res.push_back(mp(a[i].fi, a[i].se));
            use[a[i].se] = true;
        }
        i ++ ;
    }
    while(j < b.size() && res.size() < K){
        if(!use[b[j].se]){
            res.push_back(mp(b[j].fi + 1, b[j].se));
            use[b[j].se] = true;
        }
        j ++ ;
    }
    
    for(auto p : res)
        use[p.se] = false;
    return res;
}

int main(){
    fastIO;
    int n, m, q;
    cin >> n >> m >> q;
    int u, v;
    for(int i = 0 ; i < m ; i ++ ){
        cin >> u >> v;
        T[v].push_back(u);
    }
    for(int i = 1; i <= n; i ++ ){
        best[i].push_back({0, i});
        for(auto p : T[i]){
            best[i] = unite(best[i], best[p]);
        }
    }
    int x, k;
    int d;
    int ret;
    vector<int> id;
    for(int qq = 0 ; qq < q; qq ++ ){
        cin >> x >> k;
        id.clear();
        for(int j = 0 ; j < k ; j ++ ){
            cin >> d;
            id.push_back(d);
        }
        for(auto p : id) ban[p] = true;
        
        if(k >= K){
            for(int i = 1; i <= n; i ++ )
                dp[i] = -inf;
            dp[x] = 0;
            ret = -1;
            for(int i = n; i >= 1; i -- ){
                if(!ban[i])ret = max(ret, dp[i]);
                for(auto vv : T[i]){
                    dp[vv] = max(dp[vv], dp[i] + 1);
                }
            }
            
            cout << ret << "\n";
        }
        else{
            ret = -1;
            for(auto p : best[x]){
                if(!ban[p.se]){
                    ret = p.fi;
                    break;
                }
            }
            cout << ret << "\n";
        }
        for(auto p : id) ban[p] = false;
    }
    return 0;
}

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

bitaro.cpp: In function 'std::vector<std::pair<int, int> > unite(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:32:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < a.size() && j < b.size() && res.size() < K){
           ~~^~~~~~~~~~
bitaro.cpp:32:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < a.size() && j < b.size() && res.size() < K){
                           ~~^~~~~~~~~~
bitaro.cpp:52:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < a.size() && res.size() < K){
           ~~^~~~~~~~~~
bitaro.cpp:59:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(j < b.size() && res.size() < K){
           ~~^~~~~~~~~~

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