Submission #1261153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261153		Good	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1094 ms	412348 KiB

bitaro

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define rev(i, a, b) for (int i = (a); i >= (b); --i)

const ll inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

vector<bool> vis;
vi d;
vpii dist;
vector<vi> a;
vector<vpii> b;

void solve() {
    int n, m, q, u, v;
    cin >> n >> m >> q;
    a.resize(n + 1);
    b.resize(n + 1);
    dist.resize(n + 1);
    vis.resize(n + 1);
    d.resize(n + 1);
    int block = 500;
    rep(i, 0, m) {
        cin >> u >> v;
        a[v].pb(u);
    }

    vi c(n + 1, 0);
    rep(i, 1, n + 1) {
        rep(j, 0, block) {
            pii nd = {0, 0};
            int cur = 0;
            for(int &k: a[i]) {
                while(c[k] < b[k].size() && vis[b[k][c[k]].ss]) c[k]++; 
                if (c[k] < b[k].size() && b[k][c[k]].ff + 1 > nd.ff && !vis[b[k][c[k]].ss])
                    nd = {b[k][c[k]].ff + 1, b[k][c[k]].ss}, cur = k;
                else if (c[k] == b[k].size() && 1 > nd.ff && !vis[k])
                    nd = {1, k}, cur = k;
            }
 
            // cout << "filling " <<  i << ' ' << nd.ff << ' ' << nd.ss << endl;
            if (nd.ss != 0) b[i].pb(nd), vis[nd.ss] = 1, c[cur]++;
            else break;
        }
        for(int &j: a[i]) c[j] = 0;
        if (b[i].size() < block) b[i].pb({0, i});
        rep(j, 0, sz(b[i])) vis[b[i][j].ss] = 0;
    }

    // rep(i, 1, n + 1) {
    //     cout << i << " ==== ";
    //     for (pii &j: b[i]) cout << j.ss << ' ';
    //     cout << endl;
    // }

    rep(i, 1, n + 1) dist[i] = {0, i};

    while(q--) {
        int t, y;
        auto clear = [](int y) {
            rep(i, 0, y) vis[d[i]] = 0;
        };

        cin >> t >> y;
        rep(i, 0, y) cin >> d[i], vis[d[i]] = 1;
        bool flag = 0;
        for (pii &i: b[t])
            if (!vis[i.ss]) {
                cout << i.ff << '\n';
                flag = true;
                break;
            }
        if (flag) {clear(y); continue;}
        else if (b[t].size() < block) {
            clear(y);
            cout << -1 << endl;
            continue;
        }

        rep(i, 1, n + 1) {
            for (int &j: a[i]) {
                if (dist[j].ff + 1 > dist[i].ff && !vis[dist[j].ss]) 
                    dist[i] = {dist[j].ff + 1, dist[j].ss};
            }
        }

        if (!dist[t].ff && vis[t]) cout << -1 << '\n';
        else cout << dist[t].ff << '\n';
        rep(i, 1, n + 1) vis[i] = 0, dist[i] = {0, i};
   } 
}

int main() {
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    fast_io();
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

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