Submission #548873

#	Time	Username	Problem	Language	Result	Execution time	Memory
548873		nonsensenonsense1	Jail (JOI22_jail)	C++17	100 / 100	564 ms	58428 KiB

jail

#include <cstdio>
#include <cstring>
#include <vector>

const int N = 120000;
int n, q, m, dt, cur, s[N], t[N], l[N], in[N], out[N], pr[N], size[N], top[N], u[N];
std::vector<int> g[N], t1[N << 1], t2[N << 1];

void dfs0(int v) {
	size[v] = 1;
	for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] == pr[v]) g[v].erase(g[v].begin() + i);
	for (int i = 0; i < (int)g[v].size(); ++i) {
		pr[g[v][i]] = v;
		dfs0(g[v][i]);
		size[v] += size[g[v][i]];
		if (size[g[v][i]] > size[g[v][0]]) std::swap(g[v][i], g[v][0]);
	}
}

void dfs1(int v) {
	in[v] = dt++;
	for (int i = 0; i < (int)g[v].size(); ++i) {
		if (i) top[g[v][i]] = g[v][i];
		else top[g[v][i]] = top[v];
		dfs1(g[v][i]);
	}
}

void update1(int l, int r, int x) {
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) t1[l++].push_back(x);
		if (r & 1) t1[--r].push_back(x);
	}
}

void update2(int i, int x) {
	for (i += n; i; i >>= 1) t2[i].push_back(x);
}

int take(std::vector<int> &vec) {
	while (!vec.empty()) {
		if (u[vec.back()] == 2) vec.pop_back();
		else if (vec.back() == cur) {
			if (vec.size() == 1) return -1;
			if (vec.front() == vec.back()) vec.pop_back();
			else std::swap(vec.front(), vec.back());
		} else return vec.back();
	}
	return -1;
}

int get1(int i) {
	int x;
	for (i += n; i; i >>= 1) {
		x = take(t1[i]);
		if (x != -1) return x;
	}
	return -1;
}

int get2(int l, int r) {
	int x;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) {
			x = take(t2[l++]);
			if (x != -1) return x;
		}
		if (r & 1) {
			x = take(t2[--r]);
			if (x != -1) return x;
		}
	}
	return -1;
}

int lca(int u, int v) {
	while (top[u] != top[v]) {
		if (in[top[u]] < in[top[v]]) std::swap(u, v);
		u = pr[top[u]];
	}
	return in[u] < in[v] ? u : v;
}

void addpath(int v, int l, int x) {
	while (true) {
		update1(std::max(in[top[v]], in[l]), in[v] + 1, x);
		v = top[v];
		if (in[v] <= in[l]) break;
		v = pr[v];
	}
}

int getpath(int v, int l) {
	int x;
	while (true) {
		x = get2(std::max(in[top[v]], in[l]), in[v] + 1);
		if (x != -1) return x;
		v = top[v];
		if (in[v] <= in[l]) break;
		v = pr[v];
	}
	return -1;
}

bool run(int v) {
	u[v] = 1;
	int to;
	while (cur = v, (to = getpath(s[v], l[v])) != -1) if (u[to] == 1 || !run(to)) return 0;
	while (cur = v, (to = getpath(t[v], l[v])) != -1) if (u[to] == 1 || !run(to)) return 0;
	while (cur = v, (to = get1(in[s[v]])) != -1) if (u[to] == 1 || !run(to)) return 0;
	u[v] = 2;
	return 1;
}

int main() {
	scanf("%d", &q);
	while (q--) {
		scanf("%d", &n);
		for (int i = 0; i < n; ++i) g[i].clear();
		for (int i = 1; i < n; ++i) {
			int a, b;
			scanf("%d%d", &a, &b);
			--a;
			--b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		dt = 0;
		dfs0(0);
		dfs1(0);
		for (int i = 0; i < n << 1; ++i) {
			t1[i].clear();
			t2[i].clear();
		}
		scanf("%d", &m);
		for (int i = 0; i < m; ++i) {
			scanf("%d%d", s + i, t + i);
			--s[i];
			--t[i];
			l[i] = lca(s[i], t[i]);
			addpath(s[i], l[i], i);
			addpath(t[i], l[i], i);
			update2(in[t[i]], i);
		}
		memset(u, 0, m << 2);
		bool ok = 1;
		for (int i = 0; i < m; ++i) if (!u[i] && !run(i)) ok = 0;
		printf("%s\n", ok ? "Yes" : "No");
	}
	return 0;
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
jail.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
jail.cpp:122:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |    scanf("%d%d", &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |   scanf("%d", &m);
      |   ~~~~~^~~~~~~~~~
jail.cpp:137:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |    scanf("%d%d", s + i, t + i);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23