Submission #1244084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244084		lovrot	Jail (JOI22_jail)	C++20	0 / 100	712 ms	1114112 KiB

jail

#define db(...) //fprintf(stderr, __VA_ARGS__)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int LOG = 17;
const int N = 1 << LOG;

int up[N][LOG], dep[N];
int ma[N], iv[N], mrv;
vector<int> g[N], h[N];

void dfs(int u, int p) { 
	iv[u] = mrv++;
	for(int v : g[u]) { 
		if(v != p) { 
			up[v][0] = u;
			dep[v] = dep[u] + 1;
			dfs(v, u);
		}
	}
	ma[u] = mrv;
}

int lca(int a, int b) { 
	if(dep[a] > dep[b]) swap(a, b);
	for(int i = LOG - 1; i >= 0; --i) { 
		if(dep[up[b][i]] >= dep[a]) { 
			b = up[b][i];
		}
	}

	if(a == b) { return a; }

	for(int i = LOG - 1; i >= 0; --i) { 
		if(up[a][i] != up[b][i]) { 
			a = up[a][i];
			b = up[b][i];
		}
	}

	return up[a][0];
}

bool under(int a, int b) {
	return iv[a] >= iv[b] && ma[a] <= ma[b];
}

bool onpath(int a, int b, int c) {
	int anc = lca(b, c);
	return under(a, anc) && (under(b, a) || under(c, a));
}

int bio[N], s[N], t[N];
vector<int> topo;

void dag(int u) { 
	if(bio[u]) { return; }
	bio[u] = 1;
	for(int v : h[u]) { dag(v); }
	topo.PB(u);
	bio[u] = topo.size();
}

void task() {
	int n, q;
	scanf("%d", &n);

	topo.clear();
	mrv = 0;
	memset(bio, 0, sizeof(bio));
	up[1][0] = 1;
	for(int i = 1; i <= n; ++i) { g[i].clear(); }

	for(int i = 0; i < n - 1; ++i) { 
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].PB(v);
		g[v].PB(u);
	}

	dfs(1, 0);
	for(int i = 1; i < LOG; ++i)
		for(int j = 1; j <= n; ++j) { up[j][i] = up[up[j][i - 1]][i - 1]; }
	
	scanf("%d", &q);
	for(int i = 0; i < q; ++i) { 
		h[i].clear();
		scanf("%d%d", s + i, t + i);
		for(int j = 0; j < i; ++j) { 
			db("%d %d %d : %d, %d %d %d : %d\n", t[i], s[j], t[j], onpath(t[i], s[j], t[j]),
				t[j], s[i], t[i], onpath(t[j], s[i], t[i]));
			if(onpath(t[i], s[j], t[j])) { 
				h[j].PB(i); 
				if(onpath(s[i], s[j], t[j])) { 
					printf("No\n");
					return;
				}
			}
			if(onpath(t[j], s[i], t[i])) { 
				h[i].PB(j); 
				if(onpath(s[j], s[i], t[i])) { 
					printf("No\n");
					return;
				}
			}
		}
	}

	for(int i = 0; i < q; ++i) { 
		if(!bio[i]) { dag(i); }
	}

	for(int i = 0; i < q; ++i) {
		for(int j : h[i]) { 
			db("%d -> %d\n", i, j);
			if(bio[i] < bio[j]) { 
				printf("No\n");
				return;
			}
		}
	}

	printf("Yes\n");
}
	
int main() { 
	int t;
	scanf("%d", &t);
	for(; t--; ) task();
	return 0;
}

Compilation message (stderr)

jail.cpp: In function 'void task()':
jail.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
jail.cpp:84:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |                 scanf("%d%d", &u, &v);
      |                 ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
jail.cpp:96:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |                 scanf("%d%d", s + i, t + i);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~

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