Submission #1307784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307784		999captain	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	6 ms	5700 KiB

bitaro

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

const int B = 320;
bool apagados[100010];
int dp[100010];
int n,m,q;

bool comp(pair<int,int> a , pair<int,int> b){
    if(a.first < b.first){
        return false;
    }
    if(a.first > b.first){
        return true;
    }
    return (a.second < b.second);
}

vector<int> adj[100010];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1;i <= m;i++){
        int a,b;
        cin >> a >> b;
        adj[b].push_back(a);
    }
    vector<pair<int,int>> dist[100010];
    for(int i = 1;i <= n;i++){
        dist[i].push_back({0 , i});
    }
    for(int i = 1;i <= n;i++){
        for(auto u : adj[i]){
            vector<pair<int,int>> c,d;
            c.clear();
            for(auto l : dist[u]){
                c.push_back({l.first + 1,l.second});
            }
            d = dist[i];
            dist[i].clear();
            set_union(d.begin() , d.end(), c.begin(), c.end(), back_inserter(dist[i]), comp);
            if(dist[i].size() > B + 1){
                dist[i].resize(B + 1);
            }
        }
    }
    for(int i = 1;i <= n;i++){
        dist[i].push_back({-1 , 0});
    }

    for(int i = 1;i <= q;i++){
        int t,y;
        cin >> t >> y;
        vector<int> atual;
        for(int j = 1;j <= y;j++){
            int a;
            cin >> a;
            atual.push_back(a);
            apagados[a] = true;
        }
        if(y <= B){
            for(auto u : dist[t]){
                if(!apagados[u.second]){
                    cout << u.first << "\n";
                    break;
                }
            }
        }
        else{
            int ans = -1;
            for(int i = 1;i <= n;i++){
                dp[i] = 0;
            }
            for(int i = t;i <= n;i++){
                for(auto u : adj[i]){
                    dp[u] = max(dp[u] , dp[i] + 1);
                }
                if(!apagados[i]){
                    ans = max(ans , dp[i]);
                }
            }
            cout << ans << "\n";
        }
        for(auto u : atual){
            apagados[u] = false;
        }
        atual.clear();
    }
    
}

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