제출 #1286529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286529		samarthkulkarni	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	1377 ms	559712 KiB

bitaro

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("fast-math")

#define ll int
#define ld long double
#define vi vector<ll>
#define endl "\n"
#define pr pair<ll, ll>
#define ff first 
#define ss second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;
void _p(ll a){cout<<a<<endl;}
void _p(string a){cout<<a<<endl;}
void _p(ld a) {cout<<a<<endl;}
template <class T>
void _p(vector<T> a){for(T val:a)cout<<val<<" ";cout<<endl;}
#define debug(x) cout<<#x<<" -> ";_p(x)

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

vector<pr> move8 = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
vector<pr> move4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pr> move2 = {{0, 1}, {1, 0}};

void solution();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}

const int MAXN = 1e5+10;
bool vis[MAXN];
vi adj[MAXN];
vi radj[MAXN];
ll n, m, q;
ll B;
vector<pr> PDist[MAXN];


vi ord;
void dfs(ll a) {
	vis[a] = true;
	for (auto b : adj[a]) {
		if (vis[b]) continue;
		dfs(b);
	}
	ord.push_back(a);
}


ll calculate(ll T, set<ll> &temp) {
	vi dist(n+1);
	for (auto val : temp) dist[val] = -1;
	for (auto a : ord) {
		for (auto b : radj[a]) {
			if (dist[b] == -1) continue;
			dist[a] = max(dist[b] + 1, dist[a]);
		}
		if (a == T) break;
	}
	return dist[T];
}



void precomputation() {
	for (auto a : ord) {

		PDist[a].push_back({0, a});

		for (auto b : radj[a]) {
			for (auto [d, h] : PDist[b]) {
				PDist[a].push_back({d+1, h});
			}
		}

		sort(all(PDist[a]), greater<pr>());

		while (PDist[a].size() > B+1) PDist[a].pop_back();
	}
}	





void solution() {
    cin >> n >> m >> q;
    B = sqrt(n);
    while (m--) {
    	ll a, b; cin >> a >> b;
    	adj[a].push_back(b);
    	radj[b].push_back(a);
    }

   	for (int i = 1; i <= n; i++) {
   		if (!vis[i]) dfs(i);
   	}
   	reverse(all(ord));

   	precomputation();


   	while (q--) {
   		ll T, Y;
   		cin >> T >> Y;
   		set<ll> temp;
   		for (int i = 0; i < Y; i++) {
   			ll x; cin >> x; temp.insert(x);
   		}

   		if (Y >= B) {
   			cout << calculate(T, temp) << endl;
   		} else {
   			ll ans = -1;
   			for (auto [x, y] : PDist[T]) {
   				if (temp.count(y)) continue;
   				else {ans = x; break;}
   			}

   			cout << ans << endl;

   		}
   	}


}

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