제출 #1220942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220942		ssafarov	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	8 ms	14408 KiB

bitaro

#define Magic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll int
#define ld long long double
#define en '\n'
#define tsts int tetss; cin >> tetss; while(tetss--)
#define all(a) a.begin() , a.end()
#define pb push_back
#define ld long long double
#define fi first
#define se second
ll INF = 1e18;
const int N = 2e5 + 1;
const int mod = 998244353;
using namespace std;
using namespace __gnu_pbds;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; 
 
// order_of_key(n) - The number of items in a set that are strictly smaller than k
// find_by_order(k) - It returns an iterator to the ith largest element
 
ll lcm(ll a, ll b)
{
  ll gc = __gcd(a, b);
  return   a / gc * b;
}
 
ll binpow (ll a, ll n) {
  if (n == 0)
    return 1;
  if (n % 2 == 1)
    return binpow (a, n-1) * a;
  else {
    ll b = binpow (a, n/2);
    return b * b;
  }
}
 
 
ll binpow_mod(ll a, ll b, ll md)
{
    ll res = 1;
    a = a % md;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % md;
        a = (a * a) % md;
        b >>= 1;
    }
    return res;
}
 
ll in() {ll x; cin >> x; return x;};
 
ll gcd (ll a, ll b, ll & x, ll & y) {
	if (a == 0) {
		x = 0; y = 1;
		return b;
	}
	ll x1, y1;
	ll d = gcd (b%a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}
 
ll gcdinv(ll a, ll b){
	ll x, y;
	gcd(a, b, x, y);
	return x;
}
 
ll eql(ll x, ll y, bool ok){
	if(ok) return x;
	else return y;
}
 
// -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- чё
vector<vector<ll>> v(N);
vector<vector<ll>> rv(N);
vector<vector<pair<ll,ll>>> ch(N);
vector<ll> tps;
ll k;
ll us[N];
ll nus[N];

void dfs(ll x){
	us[x] = 1;
	for(auto g : v[x]){
		if(!us[g])dfs(g);
	}
	tps.pb(x);
}

void func(ll x){
	ll sz = rv[x].size();
	ll cur[sz] = {};
	for(ll i = 1; i <= k; ++i){
		ll fs = -1;
		ll sc = -1;
		for(ll j = 0; j < sz; ++j){
			ll y = rv[x][j];
			ll rsz = ch[y].size();
			while(cur[j] != rsz){
				ll z1 = ch[y][cur[j]].fi;
				ll z2 = ch[y][cur[j]].se;
				if(nus[z2] == x){
					cur[j]++;
					continue;
				}
				if(z1 >= fs){
					cur[j]++;
					fs = z1 + 1;
					sc = z2;
				}
				break;
			}
		}
		if(sc == -1) continue;
		nus[sc] = x;
		ch[x].pb({fs, sc});
	}
	if((ll)ch[x].size() < k) ch[x].pb({0, x});
}

void solve(){
	ll n, m, q; cin >> n >> m >> q;
	for(ll i = 1; i <= m; ++i){
		ll x, y; cin >> x >> y;
		v[x].pb(y);
		rv[y].pb(x);
	}
	k = min(340, n);
	for(ll i = 1; i <= n; ++i){
		if(us[i]) continue;
		dfs(i);
	}
	reverse(all(tps));
	for(auto g : tps){
		func(g);
	}
	for(ll i = 1; i <= q; ++i){
		ll x, sk; cin >> x >> sk;
		if(sk < k){
			set<ll> ban;
			for(ll i = 1; i <= sk; ++i){
				ll ck; cin >> ck;
				ban.insert(ck);
			}
			
			// if((ll)ch[x].size() <= sk){
				// cout << -1 << en;
				// continue;
			// }
			ll cans;
			for(auto g : ch[x]){
				if(ban.find(g.se) != ban.end()) continue;
				cans = g.fi;
				break;
			}
			cout << cans << en;
		}else{
			ll ban[n+12] = {};
			for(ll i = 1; i <= sk; ++i){
				ll ck; cin >> ck;
				ban[ck] = 1;
			}
			ll mx[n+12] = {};
			ll hv[n+12] = {};
			for(ll i = 1; i <= n; ++i) mx[i] = -1;
			mx[x] = 0;
			queue<ll> bfs;
			bfs.push(x);
			ll cans = -1;
			while(bfs.size()){
				ll ch = bfs.front();
				bfs.pop();
				for(auto g : rv[ch]){
					hv[g]++;
					if(hv[g] == 1) bfs.push(g);
				}
			}
			bfs.push(x);
			while(bfs.size()){
				ll ch = bfs.front();
				bfs.pop();
				if(!ban[ch]){
					cans = max(cans, mx[ch]);
				}
				for(auto g : rv[ch]){
					hv[g]--;
					mx[g] = max(mx[g], mx[ch] + 1);
					if(hv[g] == 0) bfs.push(g);
				}
			}
			cout << cans << en;
		}
	}
}

int main(){
	// freopen("fairphoto.in", "r", stdin); freopen("fairphoto.out", "w", stdout);
	Magic
	// tsts{
		solve();
		cout << endl;
	// }
}

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

bitaro.cpp:15:10: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | ll INF = 1e18;
      |          ^~~~

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