Submission #1133676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133676		MON	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	11 ms	10824 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>;


struct query{
    int id; vector<int> blocked;
    query(int a, vector<int> &b) : id(a), blocked(b) {}
};

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

vector<pii> dp[nmax];
vector<int> g[nmax]; int ans[nmax];
vector<query> queries[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;
    }

    while(dp[t].size() > lim + 1)
        dp[t].pop_back();           ///very important

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

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


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 = 0; i < q; i++){
        cin >> t >> a; vector<int> block;
        while(a--){
            cin >> b;
            block.push_back(b);
        }

        queries[t].push_back(query(i, block));
    }

    for(int i = 1; i <= n ; i++){
        
        dp[i] = {{0, i}};
        for(auto &j : g[i])
            merge(i, j);
        
        for(auto &it : queries[i]){
            for(auto &j : it.blocked)
                nah[j] = 1;
            
            ans[it.id] = ask(i);
            
            for(auto &j : it.blocked)
                nah[j] = 0;
        } 
    }

    for(int i = 0; i < q ; i++)
        cout << ans[i] << '\n';

}

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