Submission #1299697

#TimeUsernameProblemLanguageResultExecution timeMemory
1299697lmaobruhBitaro’s Party (JOI18_bitaro)C++20
100 / 100
1050 ms168996 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second
#define fo(i,a,b) for (int i = (a); i <= (b); ++i)
#define fd(i,a,b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define pb push_back
#define maxi(a,b) a=max(a,b)
#define mini(a,b) a=min(a,b)
#define er(x) cerr << #x << " = " << (x) << '\n'
#define siz(x) ((int)(x).size())
#define ve vector
#define _ << ' ' <<

const int N = 1e5+5, inf = 1e9+10, mod = 1e9+7, sq = 100;

int n, m, d[N], deg[N];
ve<int> g[N], rg[N];
ve<ii> res[N];
bool kk[N], vis[N];

ve<ii> mer(ve<ii> &a, ve<ii> b) {
    fo(i,0,siz(b)-1) b[i].fi++;
    ve<ii> c; c.reserve(min(siz(a)+siz(b),sq));
    int i=0, j=0;
    while (i<siz(a)||j<siz(b)) {
        if (i==siz(a)) {
            if (!vis[b[j].se]) c.pb(b[j]), vis[b[j].se]=1;
            j++;
        } else if (j==siz(b)) {
            if (!vis[a[i].se]) c.pb(a[i]), vis[a[i].se]=1;
            i++;
        } else if (a[i].fi>b[j].fi) {
            if (!vis[a[i].se]) c.pb(a[i]), vis[a[i].se]=1;
            i++;
        } else {
            if (!vis[b[j].se]) c.pb(b[j]), vis[b[j].se]=1;
            j++;
        }
    }
    if (siz(c)>sq) c.resize(sq);
    fo(i,0,siz(a)-1) vis[a[i].se]=0;
    fo(i,0,siz(b)-1) vis[b[i].se]=0;
    return c;
}

ve<int> topo;

void init() {
    fo(i,1,n) res[i].pb({0,i});
    queue<int> q;
    fo(i,1,n) if (deg[i]==0) q.push(i);
    while (q.size()) {
        int u = q.front(); q.pop(); topo.pb(u);
        for (int v:g[u]) {
            deg[v]--;
            if (deg[v]==0) q.push(v);
        }
    }
    for (int u:topo) {
        for (int v:g[u]) {
            res[v]=mer(res[v],res[u]);
        }
    }
}

int brute(int to) {
    fo(i,1,n) d[i]=-inf;
    d[to]=0;
    fd(i,n-1,0) {
        int u=topo[i];
        for (int v:rg[u]) {
            maxi(d[v],d[u]+1);
        }
    }
    int mx=-1;
    fo(i,1,n) if (!kk[i]) maxi(mx,d[i]);
    return mx;
}

void solve() {
    int q;
    cin >> n >> m >> q;
    fo(i,1,m) {
        int u, v; cin >> u >> v;
        g[u].pb(v); rg[v].pb(u);
        deg[v]++;
    }
    init();
    while (q--) {
        int tt, sz; cin >> tt >> sz;
        ve<int> busy(sz);
        fo(i,0,sz-1) cin >> busy[i], kk[busy[i]]=1;
        if (sz<sq) {
            int mx=-1;
            for (auto &p : res[tt]) {
                if (!kk[p.se]) {
                    maxi(mx,p.fi);
                    break;
                }
            }
            cout << mx << '\n';
        } else {
            cout << brute(tt) << '\n';
        }
        fo(i,0,sz-1) kk[busy[i]]=0;
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("a.inp","r")) {
        freopen("a.inp","r",stdin);
        freopen("a.out","w",stdout);
    }
    solve();
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen("a.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen("a.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...