Submission #928336

#	Time	Username	Problem	Language	Result	Execution time	Memory
928336		dosts	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1277 ms	423584 KiB

bitaro

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
//#define int long long
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define wtf {cout << "OK\n"; return;}
const int N = 1e5+1,MOD = 998244353,B = 250,inf  = 2e9;



vi used(N,0);
void merge(vector<pii>& v1, vector<pii>& v2) {
    int n = v1.size();
    int m = v2.size();
    int p1 = 0;
    int p2 = 0;
    vi toggle;
    vector<pii> ans;
    while (p1<n && p2 < m) {
        if (v1[p1].first > v2[p2].first) {
            if (used[v1[p1].second]) ;
            else {
                used[v1[p1].second] = 1;
                toggle.push_back(v1[p1].second);
                ans.push_back(v1[p1]);
            }
            p1++;
        }
        else {
            if (used[v2[p2].second]) ;
            else {
                used[v2[p2].second] = 1;
                toggle.push_back(v2[p2].second);
                ans.push_back(v2[p2]);
            }
            p2++;
        }
    }
    while (p1 < n) {
        if (used[v1[p1].second]);
        else {
            used[v1[p1].second] = 1;
            toggle.push_back(v1[p1].second);
            ans.push_back(v1[p1]);
        }
        p1++;
    }
    while (p2 < m) {
        if (used[v2[p2].second]);
        else {
            used[v2[p2].second] = 1;
            toggle.push_back(v2[p2].second);
            ans.push_back(v2[p2]);
        }
        p2++;
    }
    if (ans.size() > B) ans.resize(B);
    v1 = ans;
    for (auto it : toggle) used[it] = 0;
}

void solve() {
    int n,m,q;
    cin >> n >> m >> q;
    vi edges[n+1],egdes[n+1],inc(n+1,0),vis(n+1,0);
    for (int i=1;i<=m;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        egdes[b].push_back(a);
        inc[b]++;
    }
    vector<pii> gnomes[n+1];
    vector<pii> gotgnomes[n+1];
    queue<int> qq;
    vi order;
    for (int i=1;i<=n;i++) if (!inc[i]) qq.push(i);
    while (!qq.empty()) {
        int f = qq.front();
        order.push_back(f);
        gnomes[f].push_back({0,f});
        qq.pop();
        for (auto it : egdes[f]) {
            for (auto& itt : gnomes[it]) ++itt.first; 
            merge(gnomes[f],gnomes[it]);
            for (auto& itt : gnomes[it]) --itt.first;
        }
        for (auto it : edges[f]) {
            if (!vis[it]) {
                inc[it]--;
                if (!inc[it]){
                    vis[it] = 1;
                    qq.push(it);
                }
            } 
        }
    }
    vector<vector<pii>> gnomevector(n+1);
    for (int i=1;i<=n;i++) for (auto it : gnomes[i]) gnomevector[i].push_back(it);
    vi banned(n+1,0);
    while (q--) {
        int party,ban;
        cin >> party >> ban;
        vi bans(ban);
        for (int i=1;i<=ban;i++) {
            cin >> bans[i-1];
            banned[bans[i-1]] = 1;
        }
        if (ban < B) {
            //Just check possible ones
            bool broken = 0;
            for (auto it : gnomevector[party]) {
                if (!banned[it.second]) {
                    cout << it.first << '\n';
                    broken = 1;
                    break;
                }
            }
            if (!broken) cout << -1 << '\n';
        }
        else {
            //Do it again only sqrt(Y) can be like this
            vi dp(n+1,-inf);
            for (auto it : order) {
                if (!banned[it]) dp[it] = 0; 
                for (auto itt : egdes[it]) dp[it] = max(dp[it],dp[itt]+1);
            }
            cout << (dp[party]<0?-1:dp[party]) << '\n';
        }
        for (int i=1;i<=ban;i++) banned[bans[i-1]] = 0;
    }
}           
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif

    int t = 1;
    //cin >> t; 
	while (t --> 0) solve();
}

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