Submission #695312

#	Time	Username	Problem	Language	Result	Execution time	Memory
695312		GusterGoose27	Jail (JOI22_jail)	C++11	0 / 100	2 ms	3028 KiB

jail

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 12e4;
const int BITS = 17;

vector<int> edges[MAXN];
bool adj[500][500];
int n, m;
pii queries[MAXN];
int lca[MAXN][BITS];
int depth[MAXN];
vector<int> order;
bool vis[500];

class query {
public:
	int l, r;
	bool f;
	query(int l, int r, bool f) : l(l), r(r), f(f) {}
};

bool operator<(query &a, query &b) {
	return (a.l == b.l) ? (a.r > b.r) : (a.l < b.l); 
}

void dfs(int cur = 0, int p = -1) {
	for (int nxt: edges[cur]) {
		if (nxt == p) continue;
		depth[nxt] = depth[cur]+1;
		lca[nxt][0] = cur;
		dfs(nxt, cur);
	}
}

int get_lca(int x, int y) {
	if (depth[x] < depth[y]) swap(x, y);
	int diff = depth[x]-depth[y];
	int p = 0;
	while (diff) {
		if (diff & 1) x = lca[x][p];
		diff /= 2;
		p++;
	}
	if (x == y) return x;
	for (int i = 16; i >= 0; i--) {
		if (lca[x][i] != lca[y][i]) {
			x = lca[x][i];
			y = lca[y][i];
		}
	}
	return lca[x][0];
}

int dist(int x, int y) {
	return depth[x]+depth[y]-2*depth[get_lca(x, y)];
}

bool on_seg(int a, int b, int c) {
	return dist(a, b) == dist(a, c)+dist(b, c);
}

void dfs2(int cur) {
	vis[cur] = 1;
	for (int i = 0; i < m; i++) {
		if (!vis[i] && adj[cur][i]) dfs2(i);
	}
	order.push_back(cur);
}

int main() {
	int t; cin >> t;
	while (t--) {
		bool s1 = 1;
		cin >> n;
		for (int i = 0; i < n; i++) edges[i].clear();
		for (int i = 0; i < n-1; i++) {
			int x, y; cin >> x >> y;
			x--; y--;
			edges[x].push_back(y);
			edges[y].push_back(x);
			if (y-x != 1) s1 = 0;
		}
		cin >> m;
		for (int i = 0; i < m; i++) {
			int x, y; cin >> x >> y;
			queries[i] = pii(x-1, y-1);
		}
		if (0) {
			vector<query> sorted;
			for (int i = 0; i < m; i++) {
				if (queries[i].first > queries[i].second) sorted.push_back(query(queries[i].second, queries[i].first, 1));
				else sorted.push_back(query(queries[i].first, queries[i].second, 0));
			}
			sort(sorted.begin(), sorted.end());
			int r[2];
			r[0] = r[1] = -1;
			bool ans = 1;
			for (query q: sorted) {
				if (r[q.f] >= q.r || r[!q.f] >= q.l) {
					ans = 0;
					break;
				}
				r[q.f] = q.r;
			}
			if (ans) {
				cout << "Yes\n";
			}
			else cout << "No\n";
		}
		else if (m <= 500) {
			dfs();
			for (int i = 1; i < BITS; i++) {
				for (int j = 0; j < n; j++) {
					lca[j][i] = lca[lca[j][i-1]][i-1];
				}
			}
			for (int i = 0; i < m; i++) fill(adj[i], adj[i]+m, 0);
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < m; j++) {
					if (i == j) continue;
					if (on_seg(queries[i].first, queries[i].second, queries[j].first) || on_seg(queries[j].first, queries[j].second, queries[i].second)) adj[i][j] = 1;
				}
			}
			fill(vis, vis+m, 0);
			order.clear();
			for (int i = 0; i < m; i++) {
				if (!vis[i]) dfs2(i);
			}
			bool ans = 1;
			for (int i = 0; i < m && ans; i++) {
				for (int j = i+1; j < m && ans; j++) {
					if (adj[order[i]][order[j]]) ans = 0;
				}
			}
			if (ans) cout << "YES\n";
			else cout << "NO\n";
		}
		else {
			srand(0);
			if (rand()%2) cout << "YES\n";
			else cout << "NO\n";
		}
	}
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:77:8: warning: variable 's1' set but not used [-Wunused-but-set-variable]
   77 |   bool s1 = 1;
      |        ^~

• 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