Submission #790393

#	Time	Username	Problem	Language	Result	Execution time	Memory
790393		anton	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1550 ms	57264 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>

const int MAX_N = 1e5;
const int SQRT = 50;
const int INF = (1<<30)-1;
int n, m, q, dp[MAX_N];
vector<vector<int>> ch;
vector<vector<pii>> f;
bool ok[MAX_N];

void long_c(){
    for(int i = 0; i<n; i++){
        if(ok[i]){
            dp[i] = 0;
        }
        else{
            dp[i] = -INF;
        }
        for(auto e: ch[i]){
            dp[i] =max(dp[i], dp[e]+1);
        }
    }
}

struct Node{
    int first, second;
    int ch;

    Node(int _f, int _s, int _c){
        first = _f;
        second = _s;
        ch = _c;
    }

    bool operator<(const Node& b)const{
        if(first!=b.first){
            return first>b.first;
        }
        return second<b.second;
    }
};

void calc_f(){
    auto cmp=[&](pii& a, pii&b){return a>b;};

    for(int i = 0; i<n; i++){
        
        vector<pii> r;
        int rs = 0;
        for(auto e: ch[i]){
            rs += f[e].size();
        }
        r.reserve(rs);
        for(auto e: ch[i]){
            r.insert(r.end(), f[e].begin(), f[e].end());
        }
        sort(r.begin(), r.end(), cmp);
        f[i].reserve(SQRT);
        for(int j =0; j<r.size(); j++){
            if(ok[r[j].second]){
                f[i].push_back(pii(r[j].first+1, r[j].second));
                ok[r[j].second] =false;
            }
            if(f[i].size()==SQRT){
                break;
            }
        }
        if(f[i].size()<SQRT){
            f[i].push_back(pii(0, i));
        }

        for(auto e:f[i]){
            ok[e.second] =true;
        }
    }
}

int short_c(int id){
    for(auto e: f[id]){
        if(ok[e.second]){
            return e.first;
        }
    }
    return -1;
}



signed main(){
    cin>>n>>m>>q;

    ch.resize(n);
    f.resize(n);
    fill(ok, ok+MAX_N, true);

    
    
    for(int i = 0; i<m; i++){
        int a, b;
        cin>>a>>b;
        ch[b-1].push_back(a-1);
    }
    calc_f();
    for(int i = 0; i<q; i++){
        int t, y;
        cin>>t>>y;
        t--;

        vector<int> rem(y);
        for(int i = 0; i<y; i++){
            cin>>rem[i];
            rem[i]--;
            ok[rem[i]] = false;
        }

        if(y<SQRT-2){
            cout<<short_c(t)<<endl;
        }
        else{
            long_c();

            cout<<max(dp[t], -1)<<endl;
        }

        for(auto e: rem){
            ok[e] = true;
        }
    }

}

Compilation message (stderr)

bitaro.cpp: In function 'void calc_f()':
bitaro.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j =0; j<r.size(); j++){
      |                       ~^~~~~~~~~

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