Submission #1107634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107634		vladilius	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1629 ms	421688 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);
    }
    
    for (int i = 1; i <= n; i++){
        sort(g[i].begin(), g[i].end(), greater<int>());
    }

    const int S = 300;
    vector<bool> ban(n + 1), used(n + 1);
    vector<int> out(n + 1);
    function<int(int)> solve = [&](int v){
        if (used[v]) return out[v];
        used[v] = 1;
        int mx = -ban[v];
        for (int i: g[v]){
            int k = solve(i);
            if (k != -1){
                mx = max(mx, k + 1);
            }
        }
        out[v] = mx;
        return mx;
    };
    
    vector<pii> A[n + 1];
    vector<int> f(n + 1, -1), p(n + 1), all;
    priority_queue<pii> pq;
    function<void(int)> dfs = [&](int v){
        for (int i: g[v]){
            for (auto [c, j]: A[i]){
                if (f[j] == -1){
                    all.pb(j);
                }
                f[j] = max(f[j], c);
            }
        }
        for (int i: g[v]){
            p[i] = 0;
            while (p[i] < A[i].size()){
                if (A[i][p[i]].ff == f[A[i][p[i]].ss]){
                    pq.push({A[i][p[i]].ff, i});
                    f[A[i][p[i]].ss] = -1;
                    break;
                }
                p[i]++;
            }
        }
        while (A[v].size() < S && !pq.empty()){
            auto [c, i] = pq.top(); pq.pop();
            A[v].pb({c + 1, A[i][p[i]].ss});
            p[i]++;
            while (p[i] < A[i].size()){
                if (A[i][p[i]].ff == f[A[i][p[i]].ss]){
                    pq.push({A[i][p[i]].ff, i});
                    f[A[i][p[i]].ss] = -1;
                    break;
                }
                p[i]++;
            }
        }
        
        if (A[v].size() < S){
            A[v].pb({0, v});
        }
        while (!pq.empty()) pq.pop();
        for (int i: all) f[i] = -1;
        all.clear();
    };
    
    for (int i = 1; i <= n; i++) 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){
            fill(used.begin(), used.end(), 0);
            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:56: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]
   56 |             while (p[i] < A[i].size()){
bitaro.cpp:69: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]
   69 |             while (p[i] < A[i].size()){

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