Submission #1307788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307788		999captain	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	969 ms	527128 KiB

bitaro

#include<bits/stdc++.h>
#define int long long 
using namespace std;
typedef pair<int,int> pii;
const int B = 320;
bool apagados[100010];
bool ok[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<pii> juntar(vector<pii> a, vector<pii> b){
    int ini1 = 0,ini2 = 0;
    vector<pii> vec;
    vector<int> app;
    while((ini1 != a.size()) || (ini2 != b.size())){
        int flag = -1;
        if(ini1 == a.size()){
            flag = 1;
        }
        else if(ini2 == b.size()){
            flag = 0;
        }
        else if(a[ini1].first > b[ini2].first){
            flag = 0;
        }
        else{
            flag = 1;
        }
        if(flag == 0){
            int s = a[ini1].second; 
            if(!ok[s]){
                app.push_back(s);
                ok[s] = true;
                vec.push_back(a[ini1]);
            }
            ini1++;
        }
        else{
            int s = b[ini2].second; 
            if(!ok[s]){
                app.push_back(s);
                ok[s] = true;
                vec.push_back(b[ini2]);
            }
            ini2++;
        }
    }
    for(auto u : app){
        ok[u] = false;
    }
    app.clear();
    return vec;
}

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();
            dist[i] = juntar(c, d);
            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] = -1e9;
            }
            dp[t] = 0;
            for(int i = t + 1;i >= 1;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: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86