Submission #928318

#	Time	Username	Problem	Language	Result	Execution time	Memory
928318		dosts	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2019 ms	39252 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 = 500,inf  = 2e9;


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]++;
    }
    set<pii> gnomes[n+1];
    set<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].insert({0,f});
        gotgnomes[f].insert({f,0});
        qq.pop();
        for (auto it : egdes[f]) {
            for (auto itt : gnomes[it]) {
                auto ittt = gotgnomes[f].lower_bound({itt.second,0});
                if (ittt != gotgnomes[f].end() && ittt->first == itt.second) {
                    if (ittt->second >= itt.first+1) continue;
                    gnomes[f].erase({ittt->second,itt.second});
                    gnomes[f].insert({itt.first+1,itt.second});
                    gotgnomes[f].erase(ittt);
                    gotgnomes[f].insert({itt.second,itt.first+1});
                }
                else {
                    gnomes[f].insert({itt.first+1,itt.second});
                    gotgnomes[f].insert({itt.second,itt.first+1});
                }
                if (gnomes[f].size() > B) gnomes[f].erase(gnomes[f].begin());
            }
        }
        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].rbegin();it != gnomevector[party].rend();it++) {
                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: 0 / 7
• Subtask 3: 0 / 86