Submission #484199

#	Time	Username	Problem	Language	Result	Execution time	Memory
484199		ian2024	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	1 ms	2636 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_PROJECT
#else
    #define cerr if(false)cerr
#endif

#define f first
#define s second
#define pb push_back

#define all(x) x.begin(), x.end()
#define ALL(x) begin(x), end(x)
#define FOR(i, a) for (int i = 0; i < (a); i++)
#define SZ(a) (int)(a).size()

typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<ll> vll;

const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1000000007;
const int sz = 1e5 + 5;

vi adj[sz];
int k;
bool vis[sz];
ii towns[sz][320];

void dfs(int u, int p) {
	for (auto v : adj[u]) {
		if (v != p) dfs(v, u);
	}
	
	vii paths;
	set<int> chosen;
	for (auto v : adj[u]) {
		if (v == p) continue;
		for (int i = 0; i < k; ++i) {
			if (towns[v][i].s == 0) break;
			if (chosen.find(towns[v][i].s) != chosen.end()) continue;
			paths.pb({1 + towns[v][i].f, towns[v][i].s});
			chosen.insert(towns[v][i].s);
		}
		paths.pb({1, v});
	}
	
	sort(all(paths), greater<ii>());
	if (u == 4) {
		for (auto x : paths) cerr << x.f << " " << x.s << endl;
	}
	
	for (int i = 0; i < min(SZ(paths), k); ++i) {
		towns[u][i] = paths[i];
	}
	vis[u] = true;
}

int dfs2(int u, int p, vi& banned) {
	auto it = lower_bound(all(banned), u);
	int ans = 0;
	if (it != banned.end() and *it == u) {
		ans = -INF;
	}
	for (auto v : adj[u]) {
		if (v == p) continue;
		auto it = lower_bound(all(banned), v);
		bool ban = (it != banned.end() and *it == v);
		int child = 1 + dfs2(v, u, banned);
		if (child == 1 and ban) continue;
		ans = max(ans, child);
	}
	return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
#ifdef LOCAL_PROJECT
#else
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif
	int n, m, q;
	cin >> n >> m >> q;
	
	k = sqrt(n);
	
	for (int i = 0; i < m; ++i) {
		int s, e;
		cin >> s >> e;
		adj[e].pb(s);
	}
	
	
	for (int i = n; i >= 1; --i) {
		if (vis[i]) continue;
		dfs(i, 0);
	}
	
	while (q--) {
		int t, y;
		cin >> t >> y;
		vi v(y);
		for (int i = 0; i < y; ++i) cin >> v[i];
		
		if (y < k) {
			bool f = false;
			for (int i = 0; i < k; ++i) {
				if (towns[t][i].s == 0) break;
				auto pos = lower_bound(all(v), towns[t][i].s);
				if (pos != v.end() and *pos == towns[t][i].s) continue;
				cout << towns[t][i].f << endl;
				f = true;
				break;
			}
			
			if (!f) cout << -1 << endl;
		} else {
			int ans = dfs2(t, 0, v);
			if (ans < 0) cout << -1;
			else cout << ans;
			cout << endl;
		}
	}
}

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