Submission #881659

#	Time	Username	Problem	Language	Result	Execution time	Memory
881659		AverageAmogusEnjoyer	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1089 ms	421288 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int B = 320, N = 1e5;
vector<pair<int,int>> longest_dist[N];
vector<int> adj[N],radj[N];
int V[N],indices[N],dist[N];
bool banned[N],taken[N]; 
void solve() {
    int n,m,q; 
    cin >> n >> m >> q;
    for (int u,v;m--;) {
        cin >> u >> v;
        assert(u < v);
        adj[--u].push_back(--v);
        radj[v].push_back(u);
    }
    for (int i=0;i<n;i++) {
        pair<int,int> best = {-1,-1};
        do {
            best = {-1,-1};
            int node_taken_from = -1;
            for (int &v: radj[i]) {
                while(indices[v] < int(longest_dist[v].size())) {
                    if (!taken[longest_dist[v][indices[v]].second]) {
                        if (longest_dist[v][indices[v]].first+1 > best.first) {
                            best = longest_dist[v][indices[v]];
                            best.first++;
                            node_taken_from = v;
                        }
                        break;
                    }
                    indices[v]++;
                }
            }    
            if (best.first != -1) {
                longest_dist[i].push_back(best);
                taken[best.second] = true;
                indices[node_taken_from]++;
            }
        } while(best.second != -1 && longest_dist[i].size() != B);
        for (int &v: radj[i]) {
            indices[v] = 0;
        }
        for (auto &[d,node]: longest_dist[i]) {
            taken[node]=false;
        }
        if (longest_dist[i].size() != B) {
            longest_dist[i].emplace_back(0,i);
        }
        assert(longest_dist[i].size() <= B);
    }
    /*
    for (int i=0;i<n;i++) {
        cout << "Node " << i+1 << "\n";
        for (auto [d,node]: longest_dist[i]) {
            cout << "Dist " << d << " from node " << node+1 << "\n";
        }
        cout << "\n";
    }
    */
    for (int u,sz;q--;) {
        cin >> u >> sz;
        --u;
        for (int i=0;i<sz;i++) {
            cin >> V[i];
            banned[--V[i]]=true;
        }
        int csz = int(longest_dist[u].size());
        if (sz >= csz && csz == B) {
            memset(dist,-1,4*(u+1));
            for (int i=0;i<=u;i++) {
                if (!banned[i]) {
                    cmax(dist[i],0);
                }
                if (dist[i] != -1) {
                    // this node CAN be reached
                    for (int &v: adj[i]) {
                        cmax(dist[v],dist[i]+1);    
                    }
                }
            }
            cout << dist[u] << "\n";
        } else {
            int p = 0;
            bool good = false;
            while(p < csz) {
                if (!banned[longest_dist[u][p].second]) { 
                    cout << longest_dist[u][p].first << "\n";
                    good = true;
                    break;
                }
                p++;
            }
            if (!good) { cout << -1 << "\n"; } 
        }
        for (int i=0;i<sz;i++) {
            banned[V[i]]=false;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    int _t = 1;
    for (int i=1;i<=_t;i++) {
        solve();
    }
}

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