Submission #695307

#	Time	Username	Problem	Language	Result	Execution time	Memory
695307		GusterGoose27	Jail (JOI22_jail)	C++11	5 / 100	148 ms	12364 KiB

jail

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 12e4;

vector<int> edges[MAXN];
int n, m;
pii queries[MAXN];

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); 
}

int main() {
	int t; cin >> t;
	bool s1 = 1;
	while (t--) {
		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 (s1) {
			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 assert(false);
	}
}

• Subtask 1: 5 / 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