Submission #564193

#	Time	Username	Problem	Language	Result	Execution time	Memory
564193		cheissmart	Jail (JOI22_jail)	C++14	100 / 100	1227 ms	364672 KiB

jail

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

bool solve() {
	int n; cin >> n;
	V<vi> G(n);
	for(int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v, u--, v--;
		G[u].PB(v);
		G[v].PB(u);
	}
	int m; cin >> m;
	vi sid(n, -1), tid(n, -1), s(m), t(m);
	for(int i = 0; i < m; i++) {
		cin >> s[i] >> t[i], s[i]--, t[i]--;
		sid[s[i]] = i, tid[t[i]] = i;
	}

	int cnt = m;

	vi d(n);
	V<vi> p(n, vi(20, -1)), idt(n, vi(20)), ids(n, vi(20));
	function<void(int, int)> dfs = [&] (int u, int pa) {
		p[u][0] = pa;
		if(p[u][0] != -1) {
			idt[u][0] = tid[u];
			ids[u][0] = sid[u];
		}
		for(int v:G[u]) if(v != pa) {
			d[v] = d[u] + 1;
			dfs(v, u);
		}
	};
	dfs(0, -1);
	V<pi> es;
	for(int j = 1; j < 20; j++) {
		for(int i = 0; i < n; i++) if(p[i][j - 1] != -1) {
			p[i][j] = p[p[i][j - 1]][j - 1];
			if(p[i][j] != -1) {
				ids[i][j] = cnt++;
				idt[i][j] = cnt++;
				es.EB(idt[i][j], idt[i][j - 1]), es.EB(idt[i][j], idt[p[i][j - 1]][j - 1]);
				es.EB(ids[i][j - 1], ids[i][j]), es.EB(ids[p[i][j - 1]][j - 1], ids[i][j]);
			}			
		}
	}

	auto up = [&] (int u, int step) {
		for(int i = 0; i < 20; i++) if(step >> i & 1)
			u = p[u][i];
		return u;
	};

	auto lca = [&] (int u, int v) {
		if(d[u] > d[v]) swap(u, v);
		for(int i = 0; i < 20; i++)
			if((d[v] - d[u]) >> i & 1)
				v = p[v][i];
		if(u == v) return u;
		for(int i = 19; i >= 0; i--)
			if(p[u][i] != p[v][i])
				u = p[u][i], v = p[v][i];
		assert(u != v && p[u][0] == p[v][0] && d[u] == d[v]);
		return p[u][0];
	};

	for(int i = 0; i < m; i++) {
		{
			int u = s[i], v = t[i], l = lca(u, v);
			if(l == v)
				l = v = up(u, d[u] - d[v] - 1);
			else
				v = p[v][0];
			for(int j = 0; j < 20; j++) if((d[u] - d[l]) >> j & 1) {
				es.EB(i, idt[u][j]);
				u = p[u][j];
			}
			assert(u == l);
			for(int j = 0; j < 20; j++) if((d[v] - d[l]) >> j & 1) {
				es.EB(i, idt[v][j]);
				v = p[v][j];
			}
			assert(v == l);
			es.EB(i, tid[l]);
		}
		{
			int u = s[i], v = t[i], l = lca(u, v);
			if(l == u)
				l = u = up(v, d[v] - d[u] - 1);
			else
				u = p[u][0];
			for(int j = 0; j < 20; j++) if((d[u] - d[l]) >> j & 1) {
				es.EB(ids[u][j], i);
				u = p[u][j];
			}
			assert(u == l);
			for(int j = 0; j < 20; j++) if((d[v] - d[l]) >> j & 1) {
				es.EB(ids[v][j], i);
				v = p[v][j];
			}
			assert(v == l);
			es.EB(sid[l], i);
		}
	}

	V<vi> g(cnt);
	for(auto[u, v]:es) {
		if(u != -1 && v != -1) {
			g[u].PB(v);
		}
	}
	vi vis(cnt);

	function<bool(int)> dfs2 = [&] (int u) {
		vis[u] = 1;
		for(int v:g[u]) {
			if(!vis[v]) {
				if(!dfs2(v))
					return false;
			} else if(vis[v] == 1)
				return false;
		}
		vis[u] = 2;
		return true;
	};
	for(int i = 0; i < cnt; i++) if(vis[i] == 0) {
		if(!dfs2(i))
			return false;
	}
	return true;
}

signed main()
{
	IO_OP;

	int t;
	cin >> t;
	while(t--)
		cout << (solve() ? "Yes" : "No") << '\n';

}

Compilation message (stderr)

jail.cpp: In function 'bool solve()':
jail.cpp:124:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |  for(auto[u, v]:es) {
      |          ^

• 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