Submission #1093223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093223		daviedu	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	6 ms	5468 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=300;
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);
    }
    map<int, int> cur;
    for (int i=1; i<=n; i++){
        cur[i] = 0;
        for (auto u: g[i]){
            for (const auto& [b, d]: best[u]){
                cur[b] = max(cur[b], d+1);
            }
        }
        for (auto it=cur.rbegin(); it != cur.rend(); it++){
            best[i].push_back(*it);
            if (sz(best[i]) == k) break;
        }
        cur.clear();
    }
    vector<int> dp (n+1);
    stack<int> removed;
    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 = max(d, ans);
            }
        }
        else{
            for (int i=city; i; i--){
                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: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86