Submission #130199

#	Time	Username	Problem	Language	Result	Execution time	Memory
130199		doowey	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2051 ms	113156 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 = 105;

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;
    for(auto &p : b)
        p.fi ++ ;
    int i = 0, j = 0;
    pii r;
    while(i < a.size() && j < b.size() && res.size() < K){
        if(a[i] > b[j]){
            r = a[i];
            i ++ ;
        }
        else{
            r = b[j];
            j ++ ;
        }
        if(use[r.se]) continue;
        use[r.se] = true;
        res.push_back(r);
    }
    while(i < a.size() && res.size() < K){
        r = a[i];
        i ++ ;
        if(use[r.se]) continue;
        use[r.se] = true;
        res.push_back(r);
    }
    while(j < b.size() && res.size() < K){
        r = b[j];
        j ++ ;
        if(use[r.se]) continue;
        use[r.se] = true;
        res.push_back(r);
    }
    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;
}

Compilation message (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:35:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < a.size() && j < b.size() && res.size() < K){
           ~~^~~~~~~~~~
bitaro.cpp:35:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < a.size() && j < b.size() && res.size() < K){
                           ~~^~~~~~~~~~
bitaro.cpp:48:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < a.size() && res.size() < K){
           ~~^~~~~~~~~~
bitaro.cpp:55: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