Submission #548710

#	Time	Username	Problem	Language	Result	Execution time	Memory
548710		nonsensenonsense1	Jail (JOI22_jail)	C++17	61 / 100	5041 ms	28872 KiB

jail

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

const int N = 120000;
const int LG = 17;
int n, q, m, s[N], t[N], l[N], in[N], out[N], f[LG][N], u[N];
std::vector<int> g[N];

void dfs(int v) {
	static int dt = 0;
	in[v] = dt++;
	for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != f[0][v]) {
		f[0][g[v][i]] = v;
		dfs(g[v][i]);
	}
	out[v] = dt;
}

bool par(int u, int v) {
	return in[u] <= in[v] && out[u] >= out[v];
}

int lca(int u, int v) {
	if (par(u, v)) return u;
	for (int i = LG - 1; i >= 0; --i) if (!par(f[i][u], v)) u = f[i][u];
	return f[0][u];
}

bool on(int x, int i) {
	return x == l[i] || (par(x, s[i]) != par(x, t[i]));
}

bool dfs1(int v) {
	u[v] = 1;
	for (int i = 0; i < (int)g[v].size(); ++i) 
		if (u[g[v][i]] == 1 || !u[g[v][i]] && !dfs1(g[v][i])) 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);
		}
		dfs(0);
		for (int j = 1; j < LG; ++j) for (int i = 0; i < n; ++i) f[j][i] = f[j - 1][f[j - 1][i]];
		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]);
		}
		for (int i = 0; i < m; ++i) g[i].clear();
		for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) if (i != j && (on(t[i], j) || on(s[j], i))) g[i].push_back(j);
		memset(u, 0, m << 2);
		bool ok = 1;
		for (int i = 0; i < m; ++i) if (!u[i] && !dfs1(i)) ok = 0;
		printf("%s\n", ok ? "Yes" : "No");
	}
	return 0;
}

Compilation message (stderr)

jail.cpp: In function 'bool dfs1(int)':
jail.cpp:37:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |   if (u[g[v][i]] == 1 || !u[g[v][i]] && !dfs1(g[v][i])) return 0;
      |                          ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
jail.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
jail.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |    scanf("%d%d", &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d", &m);
      |   ~~~~~^~~~~~~~~~
jail.cpp:59:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |    scanf("%d%d", s + i, t + i);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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