Submission #1161804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161804		ReLice	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	8 ms	5960 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;

    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});
        }

        map<ll,ll> mp;
        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--;
                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]++;

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

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

    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] = -1;
                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 = dis;
                    break;
                }
            }
        }

        cout<<ans<<endl;
    }
}

signed main(){
    start();

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

    while(t--) solve();
}

/*

*/

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