Submission #1094147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094147		BLOBVISGOD	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1410 ms	94032 KiB

bitaro

#include "bits/stdc++.h"
#pragma GCC optimize("O3")
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int oo = 1e9;
const int B = 101;
const int N = 2e5+10;
bool seen[N];
int dp[N];

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,m,q; cin >> n >> m >> q;
    vvi rev(n);
    rep(i,0,m){
        int s,e; cin >> s >> e;
        s--,e--;
        rev[e].push_back(s);
    }

    vector<vector<array<int,2>>> prec(n);
    for(auto& v : prec) v.reserve(B+2);
    rep(i,0,n){
        vector<array<int,2>> cur = {{-1,i}};
        for (auto to : rev[i]) cur.insert(end(cur),all(prec[to]));
        sort(all(cur));
        reverse(all(cur));
        for(int j = 0; j < sz(cur) and sz(prec[i]) < B+2; ++j) {
            auto [v,at] = cur[j];
            if (!seen[at]){
                seen[at] = 1;
                prec[i].push_back({v+1,at});
            }
        }
        for(auto [v,at] : prec[i]) seen[at] = 0;
    }

    while(q--){
        int t,y; cin >> t >> y;
        t--;
        vector<int> c(y);
        rep(i,0,y) cin >> c[i], c[i]--;
        if (y>B){
            fill(dp,dp+t+1,0);
            for(auto at : c) dp[at] = -oo;
            for(int i = 0; i <= t; ++i){
                for(auto to : rev[i]) dp[i] = max(dp[i],dp[to]+1);
            }
            if (dp[t]<0) cout << "-1\n";
            else cout << dp[t] << '\n';
        }else{
            bool done = 0;
            for(auto [v, at] : prec[t])
                if (!binary_search(all(c),at)){
                    cout << v << '\n';
                    done = 1;
                    break;
            }if (!done){
                cout << "-1\n";
            }
        }
    }
}

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