Submission #932296

#	Time	Username	Problem	Language	Result	Execution time	Memory
932296		vjudge1	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1890 ms	420408 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define fi first
#define se second
#define blsiz 450

typedef pair<int, int> ii;

int n, m, q, ac[N], d[N], del[N];
vector<int> adj[N], radj[N], lit;
vector<ii> gt[N];

bool cmp(int& a, int & b){
	return d[a] > d[b];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++){
    	int u, v;
    	cin >> u >> v;
    	adj[u].push_back(v);
    	radj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++){
    	lit.clear();
    	lit.push_back(i);
    	for (auto x : radj[i]){
    		for (auto xx : gt[x]){
    			int u = xx.se;
    			int du = xx.fi;
    			if (ac[u] != i){
    				d[u] = du + 1;
    				ac[u] = i;
    				lit.push_back(u);
    			}
    			else {
    				d[u] = max(d[u], du + 1);
    			}
    		}
    	}
    	sort(lit.begin(), lit.end(), cmp);
    	int siz = lit.size();
    	for (int j = 0; j < min(blsiz, siz); j++){
    		gt[i].push_back({d[lit[j]], lit[j]});
    	}
    }

    while (q--){
    	int u, k;
    	cin >> u >> k;
    	for (int i = 1; i <= k; i++){
    		int val; cin >> val;
    		del[val] = q + 1;
    	}
    	if (k < blsiz){
    		int res = -1;
    		for (auto x : gt[u]){
    			int v = x.se, dv = x.fi;
    			if (del[v] == q + 1) continue;
    			res = dv;
    			break;
    		}
    		cout << res << "\n";
    	}
    	else {
    		for (int i = 1; i <= n; i++) d[i] = -1;
    		for (int i = 1; i <= n; i++){
    			if (del[i] != q + 1){
    				d[i] = max(d[i], 0);
    			}
    			if (d[i] == -1) continue;
    			for (auto x : adj[i]){
    				d[x] = max(d[x], d[i] + 1);
    			}
    		}
    		cout << d[u] << "\n";
    	}

    }

    return 0;
}     

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