oj.uz

Submission #484182

# Submission time Handle Problem Language Result Execution time Memory
484182 2021-11-02T10:11:43 Z ian2024 Bitaro’s Party (JOI18_bitaro) C++14
0 / 100
 2 ms 2636 KB 
#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;
	for (auto v : adj[u]) {
		if (v == p) continue;
		for (int i = 0; i < k; ++i) {
			paths.pb({1 + towns[v][i].f, v});
		}
	}
	
	sort(all(paths), greater<ii>());
	for (int i = 0; i < min(k, SZ(paths)); ++i) {
		towns[u][i] = paths[i];
	}
	vis[u] = true;
}

int dfs2(int u, int p, vi& banned) {
	int ans = 0;
	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);
	}
	if (u == 2) cerr << ans;
	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];
		for (auto x : v) cerr << x << " ";
		cerr << endl;
		if (false) {
			for (int i = 0; i < k; ++i) {
				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;
				break;
			}
		} else {
			cout << dfs2(t, 0, v) << endl;
		}
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 1 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 1 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 1 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -