Submission #1087268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087268		0xZero	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	795 ms	181840 KiB

bitaro

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define each(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define over(x) {cout<<x<<'\n'; return;}
#define pb push_back
#define f first
#define s second
typedef long long ll;
typedef long double db;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
ll rng() { return uniform_int_distribution<ll>(0, INT64_MAX)(gen); }
/*const db PI = atan(1)*4;*/
/*const ll mod = 1e9+7;*/
const ll mod = 998244353;
const int mx=1e5+5, ms=200;
vi adj[mx], radj[mx];
vi qv[mx];
vi qs[mx];
pi dp[mx][ms];
int cnt[mx];
int mn[mx];
int dp2[mx];
int ans[mx];
void solve(int){
    rep(i,0,mx){
        rep(j,0,ms)dp[i][j]={-1,mx-1};
    }
    memset(mn, -1, sizeof(mn));
    int n, m, q;
    cin>>n>>m>>q;
    rep(i, 0, m){
        int a, b;cin>>a>>b;
        a--;b--;
        adj[a].pb(b);
        radj[b].pb(a);
    }
    rep(i, 0, q){
        int x, s;
        cin>>x>>s;
        x--;
        qs[x].pb(i);
        qv[i].resize(s);
        rep(j,0,s)cin>>qv[i][j], qv[i][j]--;
    }
    rep(i, 0, n){
        vi p(1,i);
        mn[i]=0;
        vpi p2;
        each(j,radj[i]){
            each(k,dp[j]){
                if(k.s==mx-1)break;
                if(mn[k.s]==-1) p.pb(k.s);
                mn[k.s]=max(mn[k.s], k.f+1);
            }
        }
        p2.resize(sz(p));
        rep(j,0,sz(p)) p2[j]={mn[p[j]], p[j]};
        sort(all(p2), greater<pi>());
        rep(j,0,min(ms, sz(p2)))dp[i][j]=p2[j];
        rep(j,0,sz(p))mn[p[j]]=-1;
        /*rep(j,0,sz(p))cout<<dp[i][j].f<<' ';cout<<'\n';*/
        
        each(j,qs[i]){
            rep(k,0,sz(qv[j]))cnt[qv[j][k]]++;
            if(sz(qv[j])<ms){
                rep(k,0,ms){
                    if(cnt[dp[i][k].s]==0){
                        ans[j]=dp[i][k].f;
                        break;
                    }
                }
            } else {
                rep(k,0,i+1){
                    dp2[k]=-1e9;
                    if(cnt[k]==0)dp2[k]=0;
                    each(l,radj[k]){
                        dp2[k]=max(dp2[k], dp2[l]+1);
                    }
                }
                ans[j]=dp2[i]>=0?dp2[i]:-1;
            }
            rep(k,0,sz(qv[j]))cnt[qv[j][k]]--;
        }
    }
    rep(i,0,q)cout<<ans[i]<<'\n';
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int tc=1;
    /*cin>>tc;*/
    while(tc--) solve(tc);
    return 0;
}

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