Submission #518246

#	Time	Username	Problem	Language	Result	Execution time	Memory
518246		fatemetmhr	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1825 ms	224924 KiB

bitaro

//  ~Be name khoda~  //
 
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int ssq   =  260;
const ll  inf   =  2e18;
 
vector <pair<int, int>> mx[maxn5], big, tmp;
int h[maxn5], ans[maxn5];
vector <int> adj[maxn5], jda[maxn5];
vector <int> tp, req[maxn5];
bool mark[maxn5];
 
inline void join(int v, int u){
	tmp.clear();
	int iv = 0, iu = 0;
	while(tmp.size() < ssq - 10  && (iv < mx[v].size() || iu < mx[u].size())){
		while(iv < mx[v].size() && mark[mx[v][iv].fi])
			iv++;
		while(iu < mx[u].size() && mark[mx[u][iu].fi])
			iu++;
			
		if(iv < mx[v].size() && (iu == mx[u].size() || mx[v][iv].se >= mx[u][iu].se + 1)){
			tmp.pb(mx[v][iv]);
			mark[mx[v][iv].fi] = true;
			iv++;
		}
		else if(iu < mx[u].size()){
			tmp.pb({mx[u][iu].fi, mx[u][iu].se + 1});
			mark[mx[u][iu].fi] = true;
			iu++;
		}
	}
	mx[v].clear();
	for(auto p : tmp){
		mx[v].pb(p);
		mark[p.fi] = false;
	}
	return;
}
 
inline void dfs(int v){
	mark[v] = true;
	for(auto u : adj[v]) if(!mark[u])
		dfs(u);
	tp.pb(v);
	return;
}
 
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n, m, q; cin >> n >> m >> q;
	for(int i = 0; i < m; i++){
		int a, b; cin >> a >> b;
		a--; b--;
		adj[a].pb(b);
		jda[b].pb(a);
	}
	
	for(int i = 0; i < n; i++){
		shuffle(all(adj[i]), rng);
		shuffle(all(jda[i]), rng);
	}
 
	for(int i = 0; i < n; i++) if(!mark[i])
		dfs(i);
	fill(mark, mark + n + 5, false);
	reverse(all(tp));
	for(auto u : tp){
		mx[u].pb({u, 0});
		for(auto v : jda[u]){
			join(u, v);
		}
	}
	memset(ans, -1, sizeof ans);
	memset(mark, false, sizeof mark);
	for(int i = 0; i < q; i++){
		int v, k; cin >> v >> k;
		v--;
		for(int j = 0; j < k; j++){
			int a; cin >> a;
			a--;
			req[i].pb(a);
			if(k < ssq)
				mark[a] = true;
		}
		if(k >= ssq){
			big.pb({i, v});
		}
		else{
			for(auto [u, h] : mx[v]) if(!mark[u]){
				ans[i] = h;
				break;
			}
			for(auto u : req[i])
				mark[u] = false;
		}
	}
	memset(mark, false, sizeof mark);
	for(auto [id, v] : big){
		memset(h, -1, sizeof h);
		for(auto u : req[id])
			mark[u] = true;
		for(auto u : tp){
			if(!mark[u])
				h[u] = 0;
			for(auto z : jda[u]) if(h[z] > -1)
				h[u] = max(h[u], h[z] + 1);
		}
		for(auto u : req[id])
			mark[u] = false;
		ans[id] = h[v];
	}
	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';
}

Compilation message (stderr)

bitaro.cpp: In function 'void join(int, int)':
bitaro.cpp:37:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  while(tmp.size() < ssq - 10  && (iv < mx[v].size() || iu < mx[u].size())){
      |                                   ~~~^~~~~~~~~~~~~~
bitaro.cpp:37:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  while(tmp.size() < ssq - 10  && (iv < mx[v].size() || iu < mx[u].size())){
      |                                                        ~~~^~~~~~~~~~~~~~
bitaro.cpp:38:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   while(iv < mx[v].size() && mark[mx[v][iv].fi])
      |         ~~~^~~~~~~~~~~~~~
bitaro.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   while(iu < mx[u].size() && mark[mx[u][iu].fi])
      |         ~~~^~~~~~~~~~~~~~
bitaro.cpp:43:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   if(iv < mx[v].size() && (iu == mx[u].size() || mx[v][iv].se >= mx[u][iu].se + 1)){
      |      ~~~^~~~~~~~~~~~~~
bitaro.cpp:43:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   if(iv < mx[v].size() && (iu == mx[u].size() || mx[v][iv].se >= mx[u][iu].se + 1)){
      |                            ~~~^~~~~~~~~~~~~~~
bitaro.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   else if(iu < mx[u].size()){
      |           ~~~^~~~~~~~~~~~~~

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