Submission #1020142

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

bitaro

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
#define ps(xxx) cout << (xxx) << endl;
const int N = 1e5+1,inf = 1e18,MOD = 998244353,B = 250; 
                 
vi edges[N],egdes[N];
vector<pii> mfs[N];
vi best(N);

vi order;

vi vis(N,0);
void topo(int node) {
    if (vis[node]) return;
    vis[node] = 1;
    for (auto it : egdes[node]) topo(it);
    order.push_back(node);
}

void calc() {
    for (int i=0;i<order.size();i++) {
        int node = order[i];
        vector<pii> ps;
        vi allnbs;
        for (auto it : egdes[node]) {
            for (auto itt : mfs[it]) {
                if (!best[itt.ss]) allnbs.push_back(itt.ss);
                best[itt.ss] = max(best[itt.ss],itt.ff+1);
            }
        }
        for (auto it : allnbs) ps.push_back({best[it],it});
        if (!ps.empty()) sort(all(ps),greater<pii>());
        if (ps.size() > B+5) ps.resize(B+5);
        swap(mfs[node],ps);
        mfs[node].push_back({0,node});
        for (auto it : egdes[node]) for (auto itt : mfs[it]) best[itt.ss] = 0;
    }
}

vi mxdist(N);
void bfs2(int root) {
    mxdist[root] = 0;
    for (int i=order.size()-1;i>=0;i--) {
        int f = order[i];
        if (f != root) mxdist[f] = -1;
        for (auto it : edges[f]) if(mxdist[it]!=-1) mxdist[f] = max(mxdist[f],mxdist[it]+1);
    }
}

void solve() {                             
    int n,m,q;
    cin >> n >> m >> q;
    for (int i=1;i<=m;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        egdes[b].push_back(a);
    }
    for (int i=1;i<=n;i++) topo(i);
    calc();
    vi banned(n+1,0);
    while (q--) {
        int node,k;
        cin >> node >> k;
        vi c(k+1);
        for (int i=1;i<=k;i++) cin >> c[i];
        for (int i=1;i<=k;i++) banned[c[i]] = 1;
        if (k <= B) {
            bool fl = 0;
            for (auto it : mfs[node]) {
                if (!banned[it.ss]) {
                    fl = 1;
                    cout << it.ff << endl;
                    break;
                }
            }
            if (!fl) cout << -1 << endl;
        }
        else {
            mxdist.assign(n+1,-1);
            bfs2(node);
            int ans = -1;
            for (int i=1;i<=n;i++) if (!banned[i]) ans = max(ans,mxdist[i]);
            cout << ans << '\n';
        }
        for (int i=1;i<=k;i++) banned[c[i]] = 0;
    }
}   
 
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message (stderr)

bitaro.cpp:12:27: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 | const int N = 1e5+1,inf = 1e18,MOD = 998244353,B = 250;
      |                           ^~~~
bitaro.cpp: In function 'void calc()':
bitaro.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0;i<order.size();i++) {
      |                  ~^~~~~~~~~~~~~

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