Submission #881632

#	Time	Username	Problem	Language	Result	Execution time	Memory
881632		AverageAmogusEnjoyer	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2061 ms	23756 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 = 90, N = 1e5;
set<pair<int,int>> longest_dist[N];
map<int,int> dist_from_node[N];
vector<int> adj[N];
int V[N],dist[N];
bool banned[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);
    }
    for (int i=0;i<n;i++) {
        if (longest_dist[i].size() != B) {
            longest_dist[i].insert(make_pair(0,i));
        }
        for (int &v: adj[i]) {
            for (auto it = longest_dist[i].begin();it != longest_dist[i].end();it++) {
                pair<int,int> C = *it;
                C.first++;
                if (dist_from_node[v][C.second] < C.first) {
                    longest_dist[v].erase(make_pair(dist_from_node[v][C.second],C.second));
                    dist_from_node[v][C.second]=C.first;
                    if (longest_dist[v].size() == B) { 
                        if ((*longest_dist[v].begin()).first < C.first) {
                            longest_dist[v].erase(longest_dist[v].begin());
                            longest_dist[v].insert(C);
                        }
                    } else {
                        longest_dist[v].insert(C);
                    }
                }
            }
        }
    }
    for (int u,sz;q--;) {
        cin >> u >> sz;
        --u;
        for (int i=0;i<sz;i++) {
            cin >> V[i];
            banned[--V[i]]=true;
        }
        if (sz >= int(longest_dist[u].size())) {
            //cout << "got in\n";
            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 {
            auto it = longest_dist[u].end();
            while(true) {
                assert(it != longest_dist[u].begin());
                it--;
                if (!banned[(*it).second]) { cout << (*it).first << "\n"; break; }      
            }
        }
        for (int i=0;i<sz;i++) {
            banned[V[i]]=false;
        }
    }
    /*
    for (int i=0;i<n;i++) {
        cout << "Node " << i << "\n";
        for (auto [d,node]: longest_dist[i]) {
            cout << "Dist " << d << " from node " << node << "\n";
        }
        cout << "\n";
    }
    */
}
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: 0 / 7
• Subtask 3: 0 / 86