Submission #1266715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266715		altern23	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2 ms	2888 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e5;
const ll INF = 4e18;
const int MOD = 998244353;

ll dp[MAXN + 5], ans[MAXN + 5];
vector<ll> adj[MAXN + 5];

bitset<100005> bd;

struct DSU{
	ll N;
	vector<ll> par;
	DSU(ll _n){
		N = _n;
		par.resize(N + 5);
		iota(par.begin(), par.end(), 0LL);
	}
	
	ll find(ll idx){
		return par[idx] == idx ? idx : par[idx] = find(par[idx]);
	}
	
	void join(ll a, ll b){
		a = find(a), b = find(b);
		if(a == b) return;
		par[b] = a;
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, M, Q; cin >> N >> M >> Q;
		vector<ll> adj[N + 5];
		
		for(int i = 1; i <= M; i++){
			ll u, v; cin >> u >> v;
			adj[v].push_back(u);
		}
		
		DSU dsu(N);
		
		vector<ll> queries[N + 5], C[Q + 5];
		
		for(int i = 1; i <= Q; i++){
			ll T; cin >> T;
			queries[T].push_back(i);
			ll X; cin >> X;
			for(int j = 1; j <= X; j++){
				ll val; cin >> val;
				C[i].push_back(val);
			}
		}
		
		for(int i = 1; i <= N; i++){
			for(auto j : adj[i]){
				dp[i] = max(dp[i], dp[j] + 1);
				dsu.join(i, j);
			}
			for(auto j : queries[i]){
				for(auto x : C[j]) bd[x] = 1;
				ans[j] = -1;
				for(int k = 1; k <= N; k++){
					if(dsu.find(i) == dsu.find(k) && !bd[k]) ans[j] = max(ans[j], dp[i] - dp[k]);
				}
				for(auto x : C[j]) bd[x] = 0;
			}
		}
		
		for(int i = 1; i <= Q; i++) cout << ans[i] << "\n";
	}
}

/*

*/

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