Submission #130309

#	Time	Username	Problem	Language	Result	Execution time	Memory
130309		doowey	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1895 ms	214600 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 = 205;
const int inf = (int)1e8;

vector<int> T[N];

int dp[N];
bool ban[N];

pii cur[K + 5];

vector<pii> ret[N];
bool use[N];

void unite(vector<pii> &a, vector<pii> b){
    int z = 0;
    int i = 0, j = 0;
    while(z <= K && i < a.size() && j < b.size()){
        if(use[a[i].se]){
            i ++ ;
            continue;
        }
        if(use[b[j].se]){
            j ++ ;
            continue;
        }
        if(a[i].fi > b[j].fi + 1){
            cur[z ++ ] = mp(a[i].fi, a[i].se);
            use[a[i].se] = true;
            i ++ ;
        }
        else{
            cur[z ++ ] = mp(b[j].fi + 1, b[j].se);
            use[b[j].se] = true;
            j ++ ;
        }
    }
    while(z <= K && i < a.size()){
        if(use[a[i].se]){
            i ++ ;
            continue;
        }
        cur[z ++ ] = mp(a[i].fi, a[i].se);
        use[a[i].se] = true;
        i ++ ;
    }
    while(z <= K && j < b.size()){
        if(use[b[j].se]){
            j ++ ;
            continue;
        }
        cur[z ++ ] = mp(b[j].fi + 1, b[j].se);
        use[b[j].se] = true;
        j ++ ;
    }
    a.clear();
    for(int t = 0 ;t < z ;t ++ ){
        a.push_back(cur[t]);
        use[cur[t].se] = false;
    }
}

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 ++ ){
        ret[i].push_back(mp(0, i));
        for(auto p : T[i]){
            unite(ret[i], ret[p]);
        }
    }
    int k;
    int st;
    int y;
    vector<int> lis;
    int res = -1;
    for(int tt = 0 ; tt < q; tt ++ ){
        cin >> st >> k;
        lis.clear();
        for(int t = 0 ;t < k; t ++ ){
            cin >> y;
            ban[y] = true;
            lis.push_back(y);
        }
        if(k >= K){
            for(int i= 1 ;i <= n; i ++ )
                dp[i] = -inf;
            dp[st] = 0;
            res = -1;
            for(int i = n; i >= 1; i -- ){
                if(!ban[i]) res = max(res, dp[i]);
                for(auto vv : T[i]){
                    dp[vv] = max(dp[vv], dp[i] + 1);
                }
            }
        }
        else{
            res = -1;
            for(auto p : ret[st]){
                if(ban[p.se]) continue;
                res = p.fi;
                break;
            }
        }
        cout << res << "\n";
        for(auto p : lis)
            ban[p] = false;
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void unite(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >)':
bitaro.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(z <= K && i < a.size() && j < b.size()){
                     ~~^~~~~~~~~~
bitaro.cpp:33:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(z <= K && i < a.size() && j < b.size()){
                                     ~~^~~~~~~~~~
bitaro.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(z <= K && i < a.size()){
                     ~~^~~~~~~~~~
bitaro.cpp:62:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(z <= K && j < b.size()){
                     ~~^~~~~~~~~~

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