QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622497#7752. The Only Way to the DestinationSatonRE 0ms3672kbC++202.4kb2024-10-08 22:09:062024-10-08 22:09:06

Judging History

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

  • [2024-10-08 22:09:06]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3672kb
  • [2024-10-08 22:09:06]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
 
struct wall
{
	int x1, x2, y;
	
	bool operator<(wall x) 
	{
		if (y != x.y)
			return y<x.y;
		
		return x1 < x.x1;
	}
	
}w[10000];
 
int n, m, k;
 
struct node
{
	int l, r, color; // 记录连续空区间的左右端点,及其颜色 
};
 
vector<node> lst, cur; // lst表示前一列的空区间, cur 表示当前枚举这一列的空区间 
 
int c, f[10000];
 
// 使用并查集,保持统一性 
int find(int x)
{
	if(x!=f[x]) f[x] = find(f[x]);
	return f[x];
}
 
void merge(int x, int y)
{
	f[find(y)] = find(x);
}
 
int findl(int l)
{
	for (int i=0; i<lst.size(); ++i)
		if (lst[i].r >= l)
			return i;
	return -1;
}
 
int findr(int r)
{
	for (int i=lst.size()-1; i>=0; --i)
	{
		if (lst[i].l <= r)
			return i;
	}
	return -1;
}
 
bool solve()
{
	if (n == 1)
		return true;
	for (int i=1; i<10000; ++i)
		f[i] = i;
		
	for (int col = 1, i = 0,lstr; col<=m; ++col)
	{
		lstr = 0; // 记录上一个墙的右端点, 因此可以计算出下一段空区间为[lstr+1, w[].x1-1]
		cur.clear();
		while(i+1<=k && w[i+1].y == col)
		{
			i++;
			if (lstr+1 <= w[i].x1-1)
			{
				cur.push_back((node){lstr+1, w[i].x1-1, -1}); // 中间有空隙 
			}
			
			lstr = w[i].x2;
		}
		if (lstr+1 <= n)
			cur.push_back((node){lstr+1, n, -1});
			
		int l, r, lidx, ridx, lstf; // 枚举空区间的左右端点,以及前一个左右区间 
		for (auto &tmp: cur)
		{
			l = tmp.l;
			r = tmp.r;
			lidx = findl(l);
			ridx = findr(r);
			lstf = -1; // 所属颜色
			
			for (int i=lidx, tl, tr;i>=0 && i<=ridx; ++i)
			{
			 //   if(lst[i].r < l) continue;
				tl = max(l, lst[i].l);
				tr = min(r, lst[i].r);
				
				if (tr - tl >= 1)
					return false;
				
				if (lstf != -1)
				{
					if (find(lst[i].color != lstf))
						merge(lstf, lst[i].color);
					else
						return false; // 两个颜色已经连通 
				}
				else
					lstf = find(lst[i].color);
			} 
			
			if (lstf != -1)
				tmp.color = lstf;
			else
			{
				tmp.color = c;
				c++;
			}
		}
		
		lst = cur; //对lst重新初始化 使其表示前一列 
	}
	return true;
}
 
int main()
{
	
	cin >> n >> m >> k;
	for (int i=1; i<=k; ++i)
	{
		cin >> w[i].x1 >> w[i].x2 >> w[i].y;
	}
	sort(w+1, w+k+1);
	
	if (solve())
		cout << "yes";
	else
		cout << "no";
		
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3672kb

input:

5 3 2
2 5 1
1 4 3

output:

yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

5 3 1
2 4 2

output:

no

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

2 4 2
2 2 1
1 1 4

output:

no

result:

ok answer is NO

Test #4:

score: -100
Runtime Error

input:

409455775 596220461 69036
72554058 85866426 497212608
54242898 110165840 236869995
68671059 127632371 324336242
39386477 208393446 248270338
151972182 327931056 231832
36658944 75335495 293646122
29512382 138875677 205628469
149151850 327396301 590717922
114980184 165064700 323939243
1771834 7016377...

output:


result: