Submission #965344

#	Time	Username	Problem	Language	Result	Execution time	Memory
965344		Alkaser_ID	Jail (JOI22_jail)	C++17	0 / 100	1256 ms	1048576 KiB

jail

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;

vector<ll> adj[N], path[N];
ll a[N], b[N], dep[N], p[N][20];
ll ind[N], curr[N];
bool vis[N], com[N];
inline void dfs1(ll i, ll pr) {
	p[i][0] = pr;
	dep[i] = dep[pr] + 1;
	for (ll j = 1; j < 20; ++j) {
		p[i][j] = p[p[i][j - 1]][j - 1];
	}
	for (ll j = 0; j < adj[i].size(); ++j) {
		if (adj[i][j] == pr) continue;
		dfs1(adj[i][j], i);
	}
}
inline ll parent(ll x, ll d) {
	if (d == 0) return x;
	for (ll j = 0; j < 20; ++j) {
		if ((1ll << j) & d) return parent(p[x][j], d - (1ll << j));
	}
}
inline ll lca(ll x, ll y) {
	if (dep[x] > dep[y]) swap(x, y);
	y = parent(y, dep[y] - dep[x]);
	if (x == y) return x;
	for (ll j = 19; j >= 0; --j) {
		if (p[x][j] != p[y][j]) {
			x = p[x][j];
			y = p[y][j];
		}
	}
	return p[x][0];
}
inline void pth(ll i) {
	ll ca = lca(a[i], b[i]);
	if (ca == a[i]) {
		ll cr = b[i];
		for (;;) {
			path[i].push_back(cr);
			cr = p[cr][0];
			if (cr == ca) break;
		}
		reverse(path[i].begin(), path[i].end());
	}
	else if (ca == b[i]) {
		ll cr = a[i];
		for (;;) {
			cr = p[cr][0];
			path[i].push_back(cr);
			if (cr == ca) break;
		}
	}
	else {
		ll cr = a[i];
		for (;;) {
			cr = p[cr][0];
			path[i].push_back(cr);
			if (cr == ca) break;
		}
		vector<ll> as; 
		cr = b[i];
		for (;;) {
			as.push_back(cr);
			cr = p[cr][0];
			if (cr == ca) break;
		}
		reverse(as.begin(), as.end());
		for (ll j = 0; j < as.size(); ++j) path[i].push_back(as[j]);
	}
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	for (; t--;) {
		ll n; cin >> n;
		for (ll i = 1; i <= n; ++i) {
			adj[i].clear(); path[i].clear();
			vis[i] = false; com[i] = false;
		}
		for (ll i = 1; i < n; ++i) {
			ll u, v; cin >> u >> v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		dfs1(1, 0);
		ll q; cin >> q;
		for (ll i = 1; i <= q; ++i) {
			cin >> a[i] >> b[i];
			pth(i);
			vis[a[i]] = true; curr[i] = a[i];
			ind[i] = 0;
		}
		bool ans = true;
		for (ll completed = 0; completed < q;) {
			bool fl = true;
			for (ll i = 1; i <= q; ++i) {
				if (com[i]) continue;
				for (;;) {
					ll dx = ind[i];
					if (vis[path[i][dx]]) break;
					vis[curr[i]] = false;
					curr[i] = path[i][dx];
					fl = false;
					vis[curr[i]] = true;
					++ind[i];
					if (ind[i] == path[i].size()) { com[i] = true; ++completed; break; }
				}
			}
			if (fl) { ans = false; break; }
		}
		if (ans) cout << "Yes\n";
		else cout << "No\n";
	}
}

Compilation message (stderr)

jail.cpp: In function 'void dfs1(ll, ll)':
jail.cpp:20:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (ll j = 0; j < adj[i].size(); ++j) {
      |                 ~~^~~~~~~~~~~~~~~
jail.cpp: In function 'void pth(ll)':
jail.cpp:77:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (ll j = 0; j < as.size(); ++j) path[i].push_back(as[j]);
      |                  ~~^~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:116:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |      if (ind[i] == path[i].size()) { com[i] = true; ++completed; break; }
      |          ~~~~~~~^~~~~~~~~~~~~~~~~
jail.cpp: In function 'll parent(ll, ll)':
jail.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^

• 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