oj.uz

Submission #557595

# Submission time Handle Problem Language Result Execution time Memory
557595 2022-05-05T14:40:05 Z DanShaders Jail (JOI22_jail) C++17
0 / 100
 2639 ms 1048576 KB 
//bs:sanitizers
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 1.25e5, M = 5 * N;

vector<int> g[N], g2[M];

char used[M];

bool dfs_cycle(int u) {
	if (used[u] == 1) {
		return false;
	}
	used[u] = 1;
	for (int v : g2[u]) {
		if (used[v] != 2 && !dfs_cycle(v)) {
			return false;
		}
	}
	used[u] = 2;
	return true;
}

int sz[N];

int dfs_sz(int u = 0, int p = -1) {
	int res = 1;
	for (int v : g[u]) {
		if (v != p) {
			res += dfs_sz(v, u);
		}
	}
	return sz[u] = res;
}

int timer, order[N], lnk[N], tout[N], parent[N];

void dfs_hld(int u = 0, int up = 0, int p = -1) {
	// cout << u << " " << up << " " << p << endl;
	order[u] = timer;
	parent[timer] = p == -1 ? -1 : order[p];
	lnk[timer] = order[up];
	++timer;
	sort(all(g[u]), [](int x, int y) {
		return sz[x] > sz[y];
	});
	bool is_first = true;
	for (int v : g[u]) {
		if (v != p) {
			dfs_hld(v, is_first ? up : v, u);
			is_first = false;
		}
	}
	tout[order[u]] = timer;
}

bool in(int x0, int y0, int x1, int y1) {
	return x0 <= x1 && y1 <= y0;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int testcases;
	cin >> testcases;
	while (testcases--) {
		int n, m;
		cin >> n;
		for (int i = 0; i < 5 * n; ++i) {
			g2[i].clear();
		}
		for (int i = 0; i < n; ++i) {
			g[i].clear();
		}
		for (int i = 1; i < n; ++i) {
			int u, v;
			cin >> u >> v;
			// cout << u << " " << v << endl;
			g[--u].push_back(--v);
			g[v].push_back(u);
		}
		timer = 0;
		dfs_sz();
		dfs_hld();
		// cout << timer << endl;
		assert(timer == n);

		cin >> m;
		for (int person = 0; person < m; ++person) {
			int u = 4 * n + person;

			int s, t;
			cin >> s >> t;
			s = order[s - 1], t = order[t - 1];

			auto use_cut = [&](int l, int r) {
				for (int i = l; i <= r; ++i) {
					if (i != s) {
						g2[u].push_back(n + i);
					}
				}
				for (int i = l; i <= r; ++i) {
					if (i != t) {
						g2[3 * n + i].push_back(u);
					}
				}
			};

			while (lnk[s] != lnk[t]) {
				// cout << s << " " << t << " " << lnk[s] << " " << lnk[t] << endl;
				if (!in(lnk[s], tout[lnk[s]], t, tout[t])) {
					use_cut(lnk[s], s);
					s = parent[lnk[s]];
				} else {
					assert(!in(lnk[t], tout[lnk[t]], s, tout[s]));
					use_cut(lnk[t], t);
					t = parent[lnk[t]];
				}
			}
			use_cut(min(s, t), max(s, t));
			// path.clear();
			// dfs(s[i], t[i]);

			// for (int u : path) {
			// 	if (u != s[i]) {
			// 		g2[4 * n + i].push_back(n + u);
			// 	}
			// }
			// for (int u : path) {
			// 	if (u != t[i]) {
			// 		g2[3 * n + u].push_back(4 * n + i);
			// 	}
			// }
			g2[n + s].push_back(u);
			g2[u].push_back(3 * n + t);
		}
		fill(used, used + 5 * n, 0);
		bool flag = true;
		for (int i = 0; i < 5 * n; ++i) {
			if (!used[i]) {
				flag &= dfs_cycle(i);
			}
		}
		cout << (flag ? "Yes\n" : "No\n");
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 10 ms 17876 KB Output is correct
3 Correct 10 ms 17904 KB Output is correct
4 Correct 21 ms 18108 KB Output is correct
5 Correct 33 ms 18004 KB Output is correct
6 Correct 11 ms 17948 KB Output is correct
7 Correct 11 ms 18020 KB Output is correct
8 Correct 13 ms 18216 KB Output is correct
9 Correct 221 ms 46412 KB Output is correct
10 Correct 1692 ms 513456 KB Output is correct
11 Correct 15 ms 18004 KB Output is correct
12 Correct 50 ms 18996 KB Output is correct
13 Correct 275 ms 112328 KB Output is correct
14 Correct 286 ms 143944 KB Output is correct
15 Runtime error 2639 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17876 KB Output is correct
2 Correct 11 ms 17876 KB Output is correct
3 Correct 11 ms 17952 KB Output is correct
4 Incorrect 13 ms 18004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17876 KB Output is correct
2 Correct 11 ms 17876 KB Output is correct
3 Correct 11 ms 17952 KB Output is correct
4 Incorrect 13 ms 18004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17876 KB Output is correct
2 Correct 11 ms 17876 KB Output is correct
3 Correct 11 ms 17952 KB Output is correct
4 Incorrect 13 ms 18004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17876 KB Output is correct
2 Correct 11 ms 17876 KB Output is correct
3 Correct 11 ms 17952 KB Output is correct
4 Incorrect 13 ms 18004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17936 KB Output is correct
2 Correct 11 ms 17888 KB Output is correct
3 Correct 10 ms 17876 KB Output is correct
4 Correct 10 ms 17896 KB Output is correct
5 Correct 15 ms 18080 KB Output is correct
6 Incorrect 10 ms 17876 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 10 ms 17876 KB Output is correct
3 Correct 10 ms 17904 KB Output is correct
4 Correct 21 ms 18108 KB Output is correct
5 Correct 33 ms 18004 KB Output is correct
6 Correct 11 ms 17948 KB Output is correct
7 Correct 11 ms 18020 KB Output is correct
8 Correct 13 ms 18216 KB Output is correct
9 Correct 221 ms 46412 KB Output is correct
10 Correct 1692 ms 513456 KB Output is correct
11 Correct 15 ms 18004 KB Output is correct
12 Correct 50 ms 18996 KB Output is correct
13 Correct 275 ms 112328 KB Output is correct
14 Correct 286 ms 143944 KB Output is correct
15 Runtime error 2639 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -