QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704206#7751. Palindrome PathdreadWA 3ms27388kbC++142.1kb2024-11-02 19:30:422024-11-02 19:30:43

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 19:30:43]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:27388kb
  • [2024-11-02 19:30:42]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e5 + 10;

int n, m, k;

struct Wall {
	int x1, x2;
	int id;
};

vector<Wall> wall[N];
vector<Wall> emp[N];

int cnt;

int par[N];

int findp(int x) {
	if(x == par[x]) return x;
	return par[x] = findp(par[x]);
}
void unite(int x, int y) {
	x = findp(x);
	y = findp(y);
	if(x == y) return;
	par[x] = y;
}

int get_len(const Wall &a, const Wall &b) {
	int l1 = a.x1, r1 = a.x2;
	int l2 = b.x1, r2 = b.x2;
	if(l1 == r2) return 3;
	else if(l2 == r1) return 1;
	else if(l1 > r2) return -2;
	else if(r1 < l2) return -1;
	else return 2;
}

void solve() {
	cin >> n >> m >> k;
	if(n == 1) {
		cout << "YES";
		return;
	}
	if(m > 2 * k + 10) {
		cout << "NO";
		return;
	}
	// cout << "asdf\n";
	for(int i = 1; i <= k; ++i) {
		int x1, x2, y;
		cin >> x1 >> x2 >> y;
		wall[y].push_back({x1, x2, 0});
	}
	// cout << "asdf\n";
	for(int i = 1; i <= m; ++i) {
		sort(wall[i].begin(), wall[i].end(), [&](const auto &a, const auto &b) {
			return a.x1 < b.x1;
		});
		int l = 1;
		for(auto t:wall[i]) {
			if(l != t.x1) {
				emp[i].push_back({l, t.x1 - 1, ++cnt});
			}
			l = t.x2 + 1;
		}
		if(l != n + 1) {
			emp[i].push_back({l, n, ++cnt});
		}
	}
	for(int i = 1; i <= cnt; ++i) {
		par[i] = i;
	}

	for(int i = 1; i < m; ++i) {
		int p1, p2;
		p1 = p2 = 0;
		while(p1 < emp[i].size() && p2 < emp[i + 1].size()) {
			// cout << p1 << " " << p2 << endl;
			int t = get_len(emp[i][p1], emp[i + 1][p2]);
			if(t == 1 || t == 3) {
				int x = emp[i][p1].id;
				int y = emp[i + 1][p2].id;
				x = findp(x);
				y = findp(y);
				if(x == y) {
					cout << "NO\n";
					return;
				}
				unite(x, y);
				if(t == 1) p1++;
				else p2++;
			} else if(t == 2) {
				cout << "NO\n";
				return;
			} else if(t == -1) {
				p1++;
			} else {
				p2++;
			}
		}
	}
	cout << "YES\n";
}

signed main() {
	// ios::sync_with_stdio(false);
	// cin.tie(0);
	// cout.tie(0);
	int t = 1;
	// cin >> t;

	while (t--)
		solve();

	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 27388kb

input:

2 2
11
11
1 1 2 2

output:

YES

result:

wrong answer Line [name=User Output] equals to "YES", doesn't correspond to pattern "-1|[LRUD]{0,1000000}"