Submission #544586

#	Time	Username	Problem	Language	Result	Execution time	Memory
544586		hollwo_pelw	Jail (JOI22_jail)	C++17	100 / 100	2253 ms	164936 KiB

jail

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen("jail.inp", "r")){
		freopen("jail.inp", "r", stdin);
		freopen("jail.out", "w", stdout);
	}
#else
	auto start = chrono::steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 1.2e5 + 5, M = N << 3;

int n, nxt[N], siz[N], par[N], tin[N], h[N], timer;
vector<int> adj[N];
// ------->>>>>>>>>>>>> <<<<<<<<<<<<<-------
void pre_dfs(int u, int p) {
	h[u] = h[par[u] = p] + 1;
	siz[u] = 1, nxt[u] = u;
	for (int &v : adj[u]) {
		if (v == p) swap(v, adj[u].back());
		if (v == p) return adj[u].pop_back();

		pre_dfs(v, u);
		siz[u] += siz[v];

		if (siz[v] > siz[adj[u][0]])
			swap(v, adj[u][0]);
	}
}

void dfs_hld(int u) {
	tin[u] = ++ timer;
	for (int &v : adj[u]) {
		if (v == adj[u][0])
			nxt[v] = nxt[u];
		dfs_hld(v);
	}
}

inline void __build_hld__() {
	timer = 0, pre_dfs(1, 0), dfs_hld(1);
}
// ------->>>>>>>>>>>>> <<<<<<<<<<<<<-------

// ------->>>>>>>>>>>>> <<<<<<<<<<<<<-------
int m, nnode, vis[M], f[N], path[N][2];
int st[M], lc[M], rc[M];
vector<int> g[2][M];

#define tm ((tl + tr) >> 1)

int build(int t, int tl = 1, int tr = n) {
	int id = ++ nnode;
	if (tl == tr) {
		if (f[tl]) {
			g[t][id].push_back(f[tl]);
			g[t ^ 1][f[tl]].push_back(id);

			// cout << "AMONGUS : ";
			// if (!t) cout << id << " -> " << f[tl] << '\n';
			// else	cout << f[tl] << " -> " << id << '\n';
		}
	} else {
		lc[id] = build(t, tl, tm);
		rc[id] = build(t, tm + 1, tr);

		g[t][id].push_back(lc[id]);
		g[t][id].push_back(rc[id]);
		g[t ^ 1][lc[id]].push_back(id);
		g[t ^ 1][rc[id]].push_back(id);

		// if (!t) cout << id << " -> " << lc[id] << '\n';
		// else	cout << lc[id] << " -> " << id << '\n';

		// if (!t) cout << id << " -> " << rc[id] << '\n';
		// else	cout << rc[id] << " -> " << id << '\n';
	}
	return id;
}

void add_edge(int l, int r, int t, int v, int id, int tl = 1, int tr = n) {
	if (l > tr || tl > r) return ;
	if (l <= tl && tr <= r) {

		// cout << "madge : ";

		// if (!t) cout << v << " -> " << id << '\n';
		// else	cout << id << " -> " << v << '\n';

		g[t][v].push_back(id);
		g[t ^ 1][id].push_back(v);
		return ;
	}
	add_edge(l, r, t, v, lc[id], tl, tm);
	add_edge(l, r, t, v, rc[id], tm + 1, tr);
}

// ------->>>>>>>>>>>>> <<<<<<<<<<<<<-------

// ------->>>>>>>>>>>>> <<<<<<<<<<<<<-------

void update(int rt, int s, int ed, int u, int v) {
	while (nxt[u] != nxt[v]) {
		if (h[nxt[u]] > h[nxt[v]])
			swap(u, v);
		add_edge(tin[nxt[v]], tin[v], s, ed, rt);
		v = par[nxt[v]];
	}
	if (tin[u] > tin[v])
		swap(u, v);
	add_edge(tin[u], tin[v], s, ed, rt);
}

// void upd(int s, int ed, int u, int v) { -> OK
// 	while (u != v) {
// 		if (h[u] > h[v]) swap(u, v);
// 		if (f[v]) {
// 			g[s][ed].push_back(f[v]);
// 			g[s ^ 1][f[v]].push_back(ed);
// 		}
// 		v = par[v];
// 	}

// 	if (f[v]) {
// 		g[s][ed].push_back(f[v]);
// 		g[s ^ 1][f[v]].push_back(ed);	
// 	}
// }

// ------->>>>>>>>>>>>> <<<<<<<<<<<<<-------

// ------->>>>>>>>>>>>> <<<<<<<<<<<<<-------

vector<int> ord;

void dfs1(int u) {
	vis[u] = 1;
	for (int v : g[0][u])
		if (!vis[v]) dfs1(v);
	ord.push_back(u);
}

void dfs2(int u, int c) {
	vis[u] = c;
	for (int v : g[1][u])
		if (!vis[v]) dfs2(v, c);
}

// ------->>>>>>>>>>>>> <<<<<<<<<<<<<-------

void Hollwo_Pelw(){
	cin >> n;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	__build_hld__();

	// for (int i = 1; i <= n; i++)
	// 	cout << tin[i] << " \n"[i == n];
	// for (int i = 1; i <= n; i++)
	// 	cout << nxt[i] << " \n"[i == n];

	cin >> m, nnode = m;
	for (int i = 1; i <= m; i++) {
		cin >> path[i][0] >> path[i][1];
	}

	for (int s = 0; s < 2; s++) {
		// cout << "\nDEBUG " << s << "\n\n";
		fill(f + 1, f + n + 1, 0);
		for (int i = 1; i <= m; i++)
			f[tin[path[i][s]]] = i;

		int rt = build(s);

		for (int i = 1; i <= m; i++)
			// upd(s, i, path[i][0], path[i][1]);
			update(rt, s, i, path[i][0], path[i][1]);
	}
	
	int cnt = 0;
	
	fill(vis + 1, vis + nnode + 1, 0);
	for (int i = 1; i <= nnode; i++)
		if (!vis[i]) dfs1(i);

	fill(vis + 1, vis + nnode + 1, 0);
	reverse(ord.begin(), ord.end());
	for (int i : ord)
		if (!vis[i]) dfs2(i, ++ cnt);
	ord.clear();

	set<int> distinct;

	for (int i = 1; i <= m; i++)
		distinct.insert(vis[i]);

	cout << ((int) distinct.size() == m ? "Yes\n" : "No\n");

	for (int i = 1; i <= n; i++)
		adj[i].clear();
	for (int i = 1; i <= nnode; i++)
		g[0][i].clear(), g[1][i].clear();
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   freopen("jail.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:16:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   freopen("jail.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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