Submission #1133698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133698		MON	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	995 ms	410808 KiB

bitaro

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#define fi first
#define se second
using namespace std;
using pii = pair<int,int>;

constexpr int nmax = 1e5 + 10;
const int lim = 317;

vector<pii> dp[nmax];
vector<int> g[nmax];  bool nah[nmax];

void merge(int t, int s){
    
    auto cs = dp[s];
    for(auto &it : cs)
        ++it.fi;
    
    vector<pii> rez; int i = 0, j = 0;
    while(i < dp[t].size() && j < cs.size()){
        if(dp[t][i] > cs[j])
            rez.push_back(dp[t][i++]);
        else rez.push_back(cs[j++]);
    }

    while(i < dp[t].size()) rez.push_back(dp[t][i++]);
    while(j < cs.size()) rez.push_back(cs[j++]);

    dp[t].clear();
    for(auto &it : rez){
        if(!nah[it.se])
            dp[t].push_back(it);
        nah[it.se] = 1;
    }

    for(auto &it : dp[t])
        nah[it.se] = 0;

    if(dp[t].size() > lim + 1)
        dp[t].resize(lim + 1);           ///very important
}

int ask(int i){
    for(auto &it : dp[i])
        if(!nah[it.se])
            return it.fi;
    return -1;
}

int brut(int i){
    vector<int> dp(nmax, -1e9);
    for(int j = 1; j <= i; j++){
        if(!nah[j]) dp[j] = 0;
        for(auto &it : g[j])
            dp[j] = max(dp[j], dp[it] + 1);
    }

    if(dp[i] < 0)
        return -1;
    return dp[i];
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int n, m, q, a, b, t; cin >> n >> m >> q;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        g[b].push_back(a);
    }

    for(int i = 1; i <= n ; i++){

        dp[i] = {{0, i}};
        for(auto &j : g[i])
            merge(i, j);
    }

    for(int i = 0; i < q; i++){
        cin >> t >> a; vector<int> block;
        for(int _ = 0; _ < a; _++){
            cin >> b; nah[b] = 1;
            block.push_back(b);
        }

        if(a <= lim) cout << ask(t) << '\n';
        else cout << brut(t) << '\n';

        for(auto &it : block)
            nah[it] = 0;
    }
}

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