Submission #790211

#	Time	Username	Problem	Language	Result	Execution time	Memory
790211		anton	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2043 ms	11324 KiB

bitaro

#include<bits/stdc++.h>

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

const int MAX_N = 1e5;
const int SQRT = 4*1e2;
const int INF = (1LL<<61LL)-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;
    }
};

int ids[MAX_N];
void calc_f(){
    for(int i = 0; i<n; i++){
        priority_queue<Node> pq;
        for(auto e: ch[i]){
            ids[e] = 0;
            //cout<<"hello"<<endl;
            pq.push(Node(f[e][0].first, f[e][0].second, e));
        }

        while(pq.size()>0 && f[i].size()<SQRT){
            //cout<<"loop"<<endl;
            auto cur = pq.top();
            pq.pop();
            if(ok[cur.second]){
                f[i].push_back(pii(cur.first+1, cur.second));
                ok[cur.second] = false;
            }
            //cout<<ids[cur.ch]<<endl;
            if(f[cur.ch].size()>=ids[cur.ch]+2){
                //cout<<"adding"<<endl;
                ids[cur.ch]++;
                pq.push(Node(f[cur.ch][ids[cur.ch]].first, f[cur.ch][ids[cur.ch]].second, cur.ch));
            }
        }
        if(f[i].size()<SQRT){
            f[i].push_back(pii(0, i));
        }

        for(auto e: f[i]){
            //cout<<e.first<<" "<<e.second<<endl;
            ok[e.second] = true;
        }
        //cout<<endl<<endl;
    }
}

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], -1LL)<<endl;
        }

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

}

Compilation message (stderr)

bitaro.cpp: In function 'void calc_f()':
bitaro.cpp:66:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   66 |             if(f[cur.ch].size()>=ids[cur.ch]+2){
      |                ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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