Submission #1093234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093234		daviedu	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1219 ms	115096 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int) (a).size()
#define ll long long
#define ld long double
#define pb push_back

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

const int mx=1e5+1;
const int k=100;
vector<int> g[mx];
vector<pair<int, int>> best[mx];
int blocked[mx];

signed main(){
    fastio;
    int n, m, q;
    cin >> n >> m >> q;
    for (int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        g[b].push_back(a);
    }
    stack<int> removed;
    vector<pair<int, int>> cur;
    for (int i=1; i<=n; i++){
        cur.push_back({0, i});
        for (auto u: g[i]){
            for (const auto& [city, d]: best[u]){
                cur.push_back({d+1, city});
            }
        }
        sort(rall(cur));
        for (const auto& [d, city]: cur){
            if (blocked[city]) continue;
            removed.push(city);
            blocked[city] = 1;
            best[i].push_back({city, d});
            if (sz(best[i]) == k) break;
        }
        cur.clear();
        while (!removed.empty()){
            blocked[removed.top()] = 0;
            removed.pop();
        }
    }
    vector<int> dp (n+1);
    while (q--){
        int city, y;
        cin >> city >> y;
        while (y--){
            int x; cin >> x;
            removed.push(x);
            blocked[x] = 1;
        }

        int ans=-1;
        if (sz(removed) < k){
            for (const auto& [b, d]: best[city]){
                if (!blocked[b]){
                    ans = d;
                    break;
                }
            }
        }
        else{
            for (int i=city; i; i--){
                if (!dp[i] && i != city) continue;
                for (auto u: g[i]) dp[u] = max(dp[u], dp[i]+1);
                if (!blocked[i]) ans = max(ans, dp[i]);
            }
            for (int i=city; i; i--) dp[i] = 0;
        }
        cout << ans << '\n';

        while (!removed.empty()){
            blocked[removed.top()] = 0;
            removed.pop();
        }
    }
}

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