Submission #544590

#	Time	Username	Problem	Language	Result	Execution time	Memory
544590		pavement	Jail (JOI22_jail)	C++17	100 / 100	3299 ms	192988 KiB

jail

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
//#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int Q, N, M, _lab, cur_scc, idx, leaf[2][700005], dep[700005], hv[700005], par[700005], pos[700005], scc_num[700005];
bool vis[700005], vis_t[700005];
vector<int> tp, adj[700005], adj2_t[700005], adj2[700005];

struct node {
	node *left, *right;
	int S, E, lab;
	node(int _s, int _e, bool _f = 0) : S(_s), E(_e) {
		lab = ++_lab;
		if (S == E) {
			leaf[_f][S] = lab;
			return;
		}
		int M = (S + E) >> 1;
		left = new node(S, M, _f);
		right = new node(M + 1, E, _f);
		if (!_f) {
			adj2[left->lab].pb(lab);
			adj2[right->lab].pb(lab);
		} else {
			adj2[lab].pb(left->lab);
			adj2[lab].pb(right->lab);
		}
	}
	void add(int l, int r, int x, bool dir) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			if (dir) adj2[lab].pb(x);
			else adj2[x].pb(lab);
			return;
		}
		left->add(l, r, x, dir);
		right->add(l, r, x, dir);
	}
} *root[2];

int init(int n, int e = -1) {
    par[n] = e;
    int sz = 1, mc = 0;
    for (auto u : adj[n]) {
        if (u == e) continue;
        dep[u] = dep[n] + 1;
        int c = init(u, n);
        if (c > mc) mc = c, hv[n] = u;
        sz += c;
    }
    return sz;
}

void decomp(int n, int h) {
    pos[n] = ++idx;
    if (hv[n] != -1) decomp(hv[n], h);
    for (auto u : adj[n]) {
        if (u == par[n] || u == hv[n]) continue;
        decomp(u, u);
    }
    hv[n] = h;
}

void add_edge(int u, int v, int x) {
    if (dep[u] > dep[v]) swap(u, v);
    for (; hv[u] != hv[v]; v = par[hv[v]]) {
		if (dep[hv[u]] > dep[hv[v]]) swap(u, v);
        root[0]->add(pos[hv[v]], pos[v], x, 0);
        root[1]->add(pos[hv[v]], pos[v], x, 1);
    }
    if (dep[u] > dep[v]) swap(u, v);
    root[0]->add(pos[u], pos[v], x, 0);
    root[1]->add(pos[u], pos[v], x, 1);
}

void dfs(int n) {
	vis[n] = 1;
	for (auto u : adj2[n])
		if (!vis[u]) dfs(u);
	tp.push_back(n);
}

void dfs_t(int n) {
	vis_t[n] = 1;
	scc_num[n] = cur_scc;
	for (auto u : adj2_t[n])
		if (!vis_t[u]) dfs_t(u);
}

main() {
	memset(hv, -1, sizeof hv);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> Q;
	while (Q--) {
		cin >> N;
		for (int i = 1, u, v; i < N; i++) {
			cin >> u >> v;
			adj[u].pb(v);
			adj[v].pb(u);
		}
		cin >> M;
		_lab = M;
		init(1);
		decomp(1, 1);
		root[0] = new node(1, N, 1);
		root[1] = new node(1, N, 0);
		for (int i = 1, S, T; i <= M; i++) {
			cin >> S >> T;
			add_edge(S, T, i);
			adj2[leaf[1][pos[S]]].pb(i);
			adj2[i].pb(leaf[0][pos[T]]);
		}
		for (int i = 1; i <= _lab; i++)
			for (int j : adj2[i]) adj2_t[j].pb(i);
		for (int i = 1; i <= N; i++)
			if (!vis[i]) dfs(i);
		reverse(tp.begin(), tp.end());
		for (int i : tp)
			if (!vis_t[i]) {
				cur_scc++;
				dfs_t(i);
			}
		set<int> ss;
		for (int i = 1; i <= M; i++) ss.insert(scc_num[i]);
		if (ss.size() == M) cout << "Yes\n";
		else cout << "No\n";
		for (int i = 1; i <= _lab; i++) {
			adj[i].clear();
			adj2[i].clear();
			adj2_t[i].clear();
			hv[i] = -1;
			dep[i] = par[i] = pos[i] = leaf[0][i] = leaf[1][i] = scc_num[i] = 0;
			vis[i] = vis_t[i] = 0;
		}
		tp.clear();
		_lab = cur_scc = idx = 0;
	}
}

Compilation message (stderr)

jail.cpp:114:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  114 | main() {
      | ^~~~
jail.cpp: In function 'int main()':
jail.cpp:150:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |   if (ss.size() == M) cout << "Yes\n";
      |       ~~~~~~~~~~^~~~

• 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