Submission #954960

#	Time	Username	Problem	Language	Result	Execution time	Memory
954960		ByeWorld	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	8 ms	22868 KiB

bitaro

#include <bits/stdc++.h>
#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<ll,ll> pii;
typedef pair<pii,ll> ipii;
const int MAXN = 3e5+10;
const ll INF = 2e18+10;
const ll LOG = 61;
const int SQRT = 150;
const int MOD = 998244353;

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

void dfs(int nw, int dis){
    if(busy[nw] != day) ans[IDX] = max(ans[IDX], 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;
        for(int j=0; j<siz; j++){
            int x; cin >> x;
            vec[i].pb(x);
        }
        if(siz >= SQRT){
            day++; day2++; IDX = i;
            for(auto in : vec[i]) busy[in] = day;
            dfs(sta, 0);
        } else {
            day++;
            for(auto in : vec[i]) busy[in] = day;
            for(auto in : best[sta]){
                if(busy[in.se] == day) continue;
                ans[i] = in.fi;
                break;
            }
        }
        cout << (ans[i] ? ans[i] : -1) << '\n';
    }
}

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