Submission #954968

#	Time	Username	Problem	Language	Result	Execution time	Memory
954968		ByeWorld	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1603 ms	119064 KiB

bitaro

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
#define ll long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,ll> ipii;
const int MAXN = 1e5+10;
const ll INF = 2e18+10;
const int SQRT = 111;

int n, m, q;
vector <int> adj[MAXN];
vector <pii> best[MAXN], que;
vector <int> vec[MAXN];
int ans;
int busy[MAXN], vis[MAXN];
int day, day2;

void dfs(int nw, int dis){
    if(busy[nw] != day) ans = max(ans, dis);
    vis[nw] = day2;
    for(auto nx : adj[nw]){
        if(vis[nx] != day2) dfs(nx, dis+1);
    }
}
signed main() {
	cin >> n >> m >> q;
	for(int i=1; i<=m; i++){
        int u, v; cin >> u >> v;
        adj[v].pb(u);
    }
    for(int i=1; i<=n; i++){
        vector <pii> coba;
        coba.pb({0, i});
        for(auto nx : adj[i]){
            for(auto in : best[nx]) coba.pb({in.fi+1, in.se});
        }
        sort(coba.rbegin(), coba.rend());
        
        day++;
        for(auto in : coba){
            if(busy[in.se] == day) continue;
            busy[in.se] = day;
            best[i].pb(in);
            if(best[i].size() == SQRT) break;
        }
    }
    // for(int i=1; i<=n; i++){
    //     cout << "\ni" << i << "\n";
    //     for(auto in:best[i]) cout << in.fi << ' ' << in.se << '\n';
    // }
    // exit(0);
    for(int i=1; i<=q; i++){
        int sta, siz; cin >> sta >> siz;
        ans = -1;
        for(int j=0; j<siz; j++){
            int x; cin >> x;
            vec[i].pb(x);
        }
        if(siz >= SQRT){
            day++; 
            vector <int> dp; 
            dp.resize(sta+2, -1); 
            
            dp[sta] = 0;
            for(int nw=sta; nw>=1; nw--){
                if(dp[nw]==-1) continue;
                for(auto nx : adj[nw]) dp[nx] = max(dp[nx], dp[nw]+1);
            }
            for(auto in : vec[i]) busy[in] = day;
            for(int nw=sta; nw>=1; nw--){
                if(busy[nw] == day) continue;
                ans = max(ans, dp[nw]);
            }
        
        } else {
            day++;
            for(auto in : vec[i]) busy[in] = day;
            for(auto in : best[sta]){
                if(busy[in.se] == day) continue;
                ans = in.fi;
                break;
            }
        }
        cout << ans << '\n';
    }
}

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