Submission #334782

#	Time	Username	Problem	Language	Result	Execution time	Memory
334782		camnguyenmeow	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1383 ms	92916 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define pii pair<int,int>
#define fr first
#define sc second
#define pow2(i) (1<<i)
#define eb emplace_back
#define mp make_pair
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(_i, _s, _n) 	for (int _i = _s; _i <= _n; ++_i)
#define FOD(_i, _s, _n)	    for (int _i = _s; _i >= _n; --_i)
#define firstbit(_mask)     __builtin_ctz(_mask)
#define lastbit(_mask)      __builtin_clz(_mask)
#define countbit(_mask)     __builtin_popcount(_mask)
int getbit(int mask, int i) {
    return (mask >> i) & 1;
}
void flipbit(int &mask, int i) {
    mask ^= (1 << i);
}
void setbit(int &mask, int i) {
    mask |= (1 << i);
}
template <typename T> inline void read(T &x) {
    x = 0; char c;
    while (!isdigit(c = getchar()));
    do x = x*10 + c - '0';
    while (isdigit(c = getchar()));
}
template <typename T> inline void write(T x) {
    if (x > 9) write(x/10);
    putchar(x % 10 + 48);
}
const int dd[4]={-1, 0, 1, 0}, dc[4]={0, 1, 0, -1};
//#define PROBLEMS            "bitaro"
#ifdef PROBLEMS
    #define cin fi
    #define cout fo
    ifstream fi (PROBLEMS".inp");
    ofstream fo (PROBLEMS".out");
#endif
#define camnguyenmeow ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
/*   /\_/\
    (= ._.)
    / >?  \>$
*/
bool cantgo[100005];
int mx[100005], d[100005], maxx = 100;
vector<int> a[100005];
vector<pii> dt[100005];
pii b[100005];
int main()
{
    camnguyenmeow
    int n, m, q, u, v, cnt;
    cin >> n >> m >> q;
    while (m--) {
        cin >> u >> v;
        a[v].push_back(u);
    }
    FOR(i, 1, n) {
        cnt = 0;
        vector<int> change;
        for (int v : a[i]) {
            if (!mx[v]) change.push_back(v);
            mx[v] = max(mx[v], 1);
            for (pii it : dt[v]) {
                if (!mx[it.sc]) change.push_back(it.sc);
                mx[it.sc] = max(mx[it.sc], it.fr + 1);
            }
        }
        cnt = 0;
        for (int v : change) {
            b[++cnt] = {mx[v], v};
            mx[v] = 0;
        }
        nth_element(b + 1, b + 1 + min(maxx, cnt), b + 1 + cnt, [&](const pii &A, const pii &B) {
            return A.fr > B.fr;
        });
        dt[i].assign(min(cnt, maxx), {0, 0});
        FOR(j, 0, min(cnt, maxx) - 1)
            dt[i][j] = b[j + 1];
    }
    while (q--) {
        int t, y;
        cin >> t >> y;
        FOR(i, 1, y) {
            cin >> u; cantgo[u] = 1;
        }
        if (y >= maxx) {
            FOR(i, 1, t) {
                d[i] = 0;
                for (int j : a[i])
                    if (!cantgo[j] || d[j])
                        d[i] = max(d[i], d[j] + 1);
            }
            if (cantgo[t] && d[t] == 0) cout << -1 <<'\n';
            else cout << d[t] <<'\n';
        }
        else {
            int ans = -1;
            for (pii i : dt[t])
                if (!cantgo[i.sc]) ans = max(ans, i.fr);
            if (!cantgo[t]) ans = max(ans, 0);
            cout << ans << '\n';
        }
        memset(cantgo, 0, sizeof(cantgo));
    }
    return 0;
}

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