Submission #1161816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161816		ReLice	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	996 ms	94616 KiB

bitaro

#include <bits/stdc++.h>
#define ll int
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}

const ll inf = 1e9;
const ll mod = 1e9 + 7;
const ll N = 1e5 + 8;
const ll b = 100;

vector<vector<ll>> g(N), rg(N);
pair<ll,ll> d[N][b];
ll dd[N];
ll id[N];

void solve() {
    ll i, j;

    ll n, m, q;
    cin>>n>>m>>q;

    for(i=0;i<m;i++){
        ll a, b;
        cin>>a>>b;

        if(a > b) swap(a, b);

        g[a].pb(b);
        rg[b].pb(a);
    }

    for(i=1;i<=n;i++){
        for(j=1;j<100;j++) d[i][j] = {-inf, -inf};
        d[i][0] = {0, i};
    }

    set<pair<pair<ll,ll>, ll>> st;

    bool mp[n + 5];
    memset(mp, false, sizeof(mp));

    for(i=1;i<=n;i++){
        if(rg[i].size() == 0) continue;
        for(auto j : rg[i]){
            id[j] = 0;
            st.ins({d[j][id[j]], j});
        }

        vector<ll> vv;
        ll x;

        for(j=0;j<100;j++){
            if(st.empty()) {
                d[i][j] = {0, i};
                break;
            }
            auto [xx, a] = *st.rbegin();
            st.erase(--st.end());

            if(mp[xx.sc]) {
                j--;
                while(id[a] < 100 && d[a][id[a]].sc >= 0 && mp[d[a][id[a]].sc]) id[a]++;
                if(id[a] < 100 && d[a][id[a]].fr >= 0) st.ins({d[a][id[a]], a});
                continue;
            }

            x = xx.fr;
            mp[xx.sc] = 1;
            vv.pb(xx.sc);

            d[i][j] = {x + 1, xx.sc};

            while(id[a] < 100 && d[a][id[a]].sc >= 0 && mp[d[a][id[a]].sc]) id[a]++;
            if(id[a] < 100 && d[a][id[a]].fr >= 0) st.ins({d[a][id[a]], a});
        }

        for(auto j : vv) mp[j] = 0;
    }

    bool f[n + 1];
    memset(f, false, sizeof(f));

    for(i=0;i<q;i++){
        ll y, t;
        cin>>t>>y;

        vector<ll> v(y);
        for(j=0;j<y;j++) cin>>v[j];

        ll ans = -1;

        if(y >= b){
            for(auto j : v) f[j] = 1;
            dd[t] = 0;

            for(j=t;j>0;j--){
                if(j != t) dd[j] = -inf;
                for(auto to : g[j]){
                    if(to > t) continue;
                    dd[j] = max(dd[j], dd[to] + 1);
                }

                if(!f[j]) ans = max(ans, dd[j]);
            }

            for(auto j : v) f[j] = 0;
        }
        else{
            for(j=0;j<100;j++){
                if(d[t][j].fr < 0) break;
                auto [dis, to] = d[t][j];

                ll low = lower_bound(all(v), to) - v.begin();

                if(low >= y || v[low] != to){
                    ans = max(dis, ans);
                    break;
                }
            }
        }

        cout<<ans<<endl;
    }
}

signed main(){
    start();

    ll t = 1;
    //cin>>t;

    while(t--) solve();
}

/*

*/

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