Submission #130050

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

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

int dp[N];

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

int deg[N];
bool ban[N];

int main(){
    fastIO;
    int n, m, q;
    cin >> n >> m >> q;
    int u[m], v[m];
    for(int i = 0 ; i < m ; i ++ ){
        cin >> u[i] >> v[i];
        T[v[i]].push_back(u[i]);
    }
    for(int i = 1; i <= n; i ++ ){
        best[i].push_back(mp(0, i));
        for(auto p : T[i]){
            best[i] = unite(best[i], best[p]);
        }
    }
    int x, k, y;
    int res;
    for(int i = 0 ;i < q; i ++ ){
        cin >> x >> k;
        vector<int> id;
        if(k >= K-2){
            for(int j = 0 ; j < k ;j  ++ ){
                cin >> y;
                id.push_back(y);
                ban[y] = true;
            }
            int res = -1;
            for(int j = 1; j <= n; j ++ ){
                dp[j] = -1;
            }
            dp[x] = 0;
            for(int j = n; j >= 1; j -- ){
                if(dp[j] == -1) continue;
                for(auto p : T[j]){
                    dp[p] = max(dp[p], dp[j] + 1);
                }
            }
            for(int j = 1; j <= n; j ++ ){
                if(ban[j]) continue;
                res = max(res, dp[j]);
            }
            cout << res << "\n";
        }
        else{
            for(int j = 0 ; j < k ; j ++ ){
                cin >> y;
                ban[y] = true;
                id.push_back(y);
            }
            res = -1;
            for(auto p : best[x]){
                if(ban[p.se]) continue;
                res = max(res, p.fi);
            }
            cout << res << "\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:29:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < a.size() && j < b.size()){
           ~~^~~~~~~~~~
bitaro.cpp:29:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < a.size() && j < b.size()){
                           ~~^~~~~~~~~~
bitaro.cpp:39:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < a.size()){
           ~~^~~~~~~~~~
bitaro.cpp:43:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(j < b.size()){
           ~~^~~~~~~~~~

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