Submission #1154487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154487		nguyn	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1255 ms	411348 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 1e5 + 5;
const int B = 316; 

int n, m, q; 
vector<int> g[N]; 
vector<pii> f[N]; 
int del[N], d[N]; 

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
    	int u, v;
    	cin >> u >> v;
    	g[v].pb(u); 
    }
    for (int i = 1; i <= n; i++) {
        f[i].pb({0, i}); 
        for (int j : g[i]) {
            for (auto it : f[j]) {
                if (d[it.S] == 0) {
                    f[i].pb({it.F + 1, it.S}); 
                }
                d[it.S] = max(d[it.S], it.F + 1); 
            } 
        }
        for (auto &it : f[i]) {
            it.F = d[it.S]; 
            d[it.S] = 0; 
        }
        sort(f[i].begin(), f[i].end(), greater<pii>());
        while(f[i].size() > B) f[i].pop_back(); 
    }
    while(q--) {
        int u, sz; 
        cin >> u >> sz; 
        vector<int> cur; 
        for (int i = 1; i <= sz; i++) {
            int v; cin >> v;
            del[v] = 1; 
            cur.pb(v); 
        }
        if (sz < B) {
            int res = -1;
            for (int i = 0; i < f[u].size(); i++) {
                if (!del[f[u][i].S]) {
                    res = f[u][i].F; 
                    break; 
                }
            }
            cout << res << '\n'; 
        }
        else {
            for (int i = 1; i <= n; i++) d[i] = -2e9; 
            for (int i = 1; i <= u; i++) {
                if (!del[i]) d[i] = 0; 
                for (int v : g[i]) {
                    d[i] = max(d[i], d[v] + 1); 
                }
            }
            if (d[u] < 0) cout << -1 << '\n';
            else cout << d[u] << '\n'; 
        }

        for (int i : cur) del[i] = 0; 
    }
}   

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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