Submission #1293154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293154		denilb	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1177 ms	143804 KiB

bitaro

#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define fastio ios::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr), cin.exceptions(cin.failbit);
using namespace std;
//using namespace __gnu_pbds;

#define endl '\n'
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-9
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define drep(i, a, b) for(int i = (b-1); i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define X first
#define Y second
#define vc vector
typedef string str;
typedef long long ll;
typedef unsigned int UI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
typedef pair<double,double> pdd;
typedef tuple<int,int,int> tii;
typedef pair<ll,ll> plli;
typedef vc<int> vi;
typedef vc<vi> vvi;
typedef vc<vvi> vvvi;
typedef vc<ll> vlli;
typedef vc<vlli> vvlli;
typedef vc<pii> vpii;
typedef vc<vpii> vvpii;
typedef vc<plli> vplli;
typedef vc<tii> vtii;
typedef vc<str> vs;
typedef vc<vs> vvs;
typedef vc<double> vd;
typedef vc<vd> vvd;
typedef vc<vvd> vvvd;

template<typename A, typename B> istream& operator>>(istream& in, pair<A,B>& p) {return in >> p.first >> p.second;}

#define INLINE   inline __attribute__ ((always_inline))
#define NOINLINE __attribute__ ((noinline))
#define DB(...) do { cerr << __VA_ARGS__ << endl; } while (0)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A,B>& p) {os << "(" << p.first << "," << p.second << ")";return os;}
template<typename A, typename B, typename C> ostream& operator<<(ostream &os, const tuple<A,B,C>& t) {os << "(" << get<0>(t) << "," << get<1>(t) << "," << get<2>(t) << ")";return os;}
template<typename T> ostream& operator<<(ostream &os, const vector<T>& v) {os << "{";rep(i,0,sz(v)) {if (i) os << ", "; os << v[i];}os << "}";return os;}
template<typename T> ostream& operator<<(ostream &os, const set<T>& s) {vector<T> vs(all(s));os << vs;return os;}
template<typename T> string i2s(T x) { ostringstream o; o << x; return o.str(); }
vs splt(string s, char c = ' ') {vs all; int p = 0, np;while ((np = (int)s.find(c, p)) >= 0) {if (np != p) all.pb(s.substr(p, np - p));p = np + 1;}if (p < sz(s)) all.pb(s.substr(p));return all;}

#define ARGS_SIZE_(a1,a2,a3,a4,a5,a6,a7,a8,a9,size,...) size
#define ARGS_SIZE(...) ARGS_SIZE_(__VA_ARGS__,9,8,7,6,5,4,3,2,1)

#define DB_1(x) #x << "=" << (x) <<
#define DB_2(x, ...) #x << "=" << (x) << ", " << DB_1(__VA_ARGS__)
#define DB_3(x, ...) #x << "=" << (x) << ", " << DB_2(__VA_ARGS__)
#define DB_4(x, ...) #x << "=" << (x) << ", " << DB_3(__VA_ARGS__)
#define DB_5(x, ...) #x << "=" << (x) << ", " << DB_4(__VA_ARGS__)
#define DB_6(x, ...) #x << "=" << (x) << ", " << DB_5(__VA_ARGS__)
#define DB_7(x, ...) #x << "=" << (x) << ", " << DB_6(__VA_ARGS__)
#define DB_8(x, ...) #x << "=" << (x) << ", " << DB_7(__VA_ARGS__)
#define DB_9(x, ...) #x << "=" << (x) << ", " << DB_8(__VA_ARGS__)
#define DB__(size, ...) DB_##size(__VA_ARGS__)
#define DB_(size, ...) DB__(size, __VA_ARGS__)
#define DBV(...) do { cerr << DB_(ARGS_SIZE(__VA_ARGS__), __VA_ARGS__) endl; } while (0)
 
// ---------- END OF TEMPLATE ----------

const int B = 100;

int main(){
    int n, m, q;
    cin >> n >> m >> q;
    vvi adj(n);
    for(int i=0; i<m; i++){
        int u, v;
        cin >> u >> v;
        adj[v-1].pb(u-1);
    }
    vi dp(n), frb(n);
    vvpii sp(n);
    vi from(n, -1);
    for(int v=0; v<n; v++){
        vi from_idx;
        sp[v].eb(0, v);
        for(int u: adj[v]){
            for(auto[len, origin]: sp[u]){
                if(from[origin] == -1){
                    from_idx.pb(origin);
                    from[origin] = len+1;
                } else {
                    from[origin] = max(from[origin], len+1);
                }
            }
        }
        for(int u: from_idx) sp[v].eb(from[u], u);
        sort(sp[v].rbegin(), sp[v].rend());
        if(sz(sp[v]) > B) sp[v].resize(B);
        for(int u: from_idx) from[u] = -1;
    }
    while(q--){
        int ans = -1;
        int r, y;
        cin >> r >> y;
        r--;
        vi ff(y);
        for(int i=0; i<y; i++){
            cin >> ff[i];
            frb[--ff[i]] = true;
        }
        if(y >= B){
            dp.assign(n, 0);
            for(int v=0; v<n; v++){
                for(int u: adj[v]){
                    if(!frb[u] || dp[u] > 0){
                        dp[v] = max(dp[v], dp[u] + 1);
                    }
                }
            }
            if(!frb[r] || dp[r] > 0) ans = dp[r];
        } else {
            for(auto[len, origin]: sp[r]){
                if(frb[origin]) continue;
                ans = len;
                break;
            }
        }
        cout << ans << endl;
        for(int i=0; i<y; i++) frb[ff[i]] = false;
    }
}

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