제출 #517855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
517855		fatemetmhr	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1391 ms	434536 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'

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int ssq   =  320;
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 && (iv < mx[v].size() || iu < mx[u].size())){
		if(iv < mx[v].size() && (iu == mx[u].size() || mx[v][iv].se >= mx[u][iu].se + 1)){
			tmp.pb(mx[v][iv]);
			iv++;
		}
		else{
			tmp.pb({mx[u][iu].fi, mx[u][iu].se + 1});
			iu++;
		}
	}
	mx[v].clear();
	for(auto p : tmp)
		mx[v].pb(p);
	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++) 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);
	
	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;
		}
	}
	for(auto [id, v] : big){
		memset(h, -1, sizeof h);
		fill(mark, mark + n + 5, false);
		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);
		}
		ans[id] = h[v];
	}
	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'void join(int, int)':
bitaro.cpp:34:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while(tmp.size() <= ssq && (iv < mx[v].size() || iu < mx[u].size())){
      |                              ~~~^~~~~~~~~~~~~~
bitaro.cpp:34:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while(tmp.size() <= ssq && (iv < mx[v].size() || iu < mx[u].size())){
      |                                                   ~~~^~~~~~~~~~~~~~
bitaro.cpp:35: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]
   35 |   if(iv < mx[v].size() && (iu == mx[u].size() || mx[v][iv].se >= mx[u][iu].se + 1)){
      |      ~~~^~~~~~~~~~~~~~
bitaro.cpp:35: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]
   35 |   if(iv < mx[v].size() && (iu == mx[u].size() || mx[v][iv].se >= mx[u][iu].se + 1)){
      |                            ~~~^~~~~~~~~~~~~~~

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