Submission #1107620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107620		vladilius	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	3 ms	592 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, q; cin>>n>>m>>q;
    vector<int> g[n + 1];
    while (m--){
        int x, y; cin>>x>>y;
        g[y].pb(x);
    }

    const int S = 300;
    vector<bool> ban(n + 1);
    function<int(int)> solve = [&](int v){
        int mx = 0;
        for (int i: g[v]){
            if (!ban[i]){
                mx = max(mx, solve(i) + 1);
            }
        }
        return mx;
    };
    
    vector<pii> A[n + 1];
    vector<int> f(n + 1);
    vector<pii> bf(n + 1, {-1, -1});
    set<pii> st;
    function<void(int)> dfs = [&](int v){
        vector<int> all;
        for (int i: g[v]){
            f[i] = 0;
            while (f[i] < A[i].size()){
                if (bf[A[i][f[i]].ss].ss < A[i][f[i]].ff){
                    if (bf[A[i][f[i]].ss].ss != -1){
                        st.erase({bf[A[i][f[i]].ss].ss, bf[A[i][f[i]].ss].ff});
                    }
                    st.insert({A[i][f[i]].ff, i});
                    bf[A[i][f[i]].ss] = {i, A[i][f[i]].ff};
                    all.pb(A[i][f[i]].ss);
                    break;
                }
                f[i]++;
            }
        }
        while (A[v].size() < S && !st.empty()){
            auto [c, i] = *prev(st.end());
            st.erase(prev(st.end()));
            A[v].pb({c + 1, A[i][f[i]].ss});
            f[i]++;
            while (f[i] < A[i].size()){
                if (bf[A[i][f[i]].ss].ss < A[i][f[i]].ff){
                    if (bf[A[i][f[i]].ss].ss != -1){
                        st.erase({bf[A[i][f[i]].ss].ss, bf[A[i][f[i]].ss].ff});
                    }
                    st.insert({A[i][f[i]].ff, i});
                    bf[A[i][f[i]].ss] = {i, A[i][f[i]].ff};
                    all.pb(A[i][f[i]].ss);
                    break;
                }
                f[i]++;
            }
        }
        
        for (int i: all) bf[i] = {-1, -1};
        all.clear();
        
        if (A[v].size() < S){
            A[v].pb({0, v});
        }
        st.clear();
    };
    
    for (int i = 1; i <= n; i++){
        if (A[i].empty()){
            dfs(i);
        }
    }

    vector<int> a;
    while (q--){
        int t, y; cin>>t>>y;
        for (int i = 0; i < y; i++){
            int x; cin>>x;
            a.pb(x);
            ban[x] = 1;
        }
        
        if (y >= S){
            cout<<solve(t)<<"\n";
        }
        else {
            int out = -1;
            for (auto [x, y]: A[t]){
                if (!ban[y]){
                    out = x;
                    break;
                }
            }
            cout<<out<<"\n";
        }
        
        for (int i: a) ban[i] = 0;
        a.clear();
    }
}

Compilation message (stderr)

bitaro.cpp: In lambda function:
bitaro.cpp:41:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             while (f[i] < A[i].size()){
bitaro.cpp:59:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             while (f[i] < A[i].size()){

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