QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#513907#9170. Cycle Gameucup-team4504#WA 0ms5632kbC++171.5kb2024-08-10 20:41:402024-08-10 20:41:42

Judging History

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

  • [2024-08-10 20:41:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5632kb
  • [2024-08-10 20:41:40]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6 + 5;
int n, m, q;
bool vis[N];
int V, E, F;
int fa[N]; int getfa(int x){return x == fa[x] ? x : fa[x] = getfa(fa[x]);}
int getid(int x, int y){
	return x * (m + 2) + y;
}
void update(int x, int y, int k){
	V += k * vis[getid(x, y)];
	E += k * (vis[getid(x, y)] && vis[getid(x - 1, y)]);
	E += k * (vis[getid(x, y)] && vis[getid(x, y - 1)]);
	E += k * (vis[getid(x, y)] && vis[getid(x + 1, y)]);
	E += k * (vis[getid(x, y)] && vis[getid(x, y + 1)]);
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	cin >> n >> m >> q;
	for (int i = 0; i <= n + 1; i++)
		for (int j = 0; j <= m + 1; j++)
			vis[getid(i, j)] = 1;
	V = (n + 2) * (m + 2), E = (n + 1) * (m + 2) + (n + 2) * (m + 1), F = (n + 1) * (m + 1);
	for (int i = 0; i < (n + 2) * (m + 2); i++) fa[i] = i;
	while (q--){
		int x, y;
		cin >> x >> y;
		bool tmp = vis[getid(x, y)];
		update(x, y, -1);
		vis[getid(x, y)] = 0;
		update(x, y, 1);
		int p[4] = {getid(x - 1, y - 1), getid(x, y - 1), getid(x - 1, y), getid(x, y)};
		set<int> st;
		for (int i = 0; i < 4; i++){
			p[i] = getfa(p[i]);
			st.insert(p[i]);
		}
		if (V - E + F - (int)st.size() + 1 != 1){
			putchar('0');
			update(x, y, -1);
			vis[getid(x, y)] = 1;
			update(x, y, 1);
		}else{
			putchar('1');
			for (int i = 0; i < 3; i++) fa[getfa(p[i])] = getfa(p[i + 1]);
			F += 1 - (int)st.size();
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 3 7
2 1
2 2
2 3
3 1
3 2
4 1
4 2

output:

1111111

result:

ok "1111111"

Test #2:

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

input:

3 3 8
1 1
1 2
1 3
2 3
3 3
3 2
3 1
2 1

output:

11111110

result:

ok "11111110"

Test #3:

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

input:

10 10 7
9 1
6 6
3 8
8 7
5 10
1 7
1 2

output:

1111111

result:

ok "1111111"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3484kb

input:

9 10 50
1 9
1 6
2 3
3 1
7 4
9 4
1 3
2 5
9 2
7 9
5 6
8 10
9 5
5 5
4 10
9 7
5 9
3 2
4 5
1 1
4 7
3 6
2 8
4 3
8 6
5 10
4 8
5 4
7 2
9 6
4 2
7 8
5 2
3 5
9 1
6 1
1 5
9 9
5 8
6 3
8 8
8 4
7 7
7 1
3 7
2 2
3 10
6 9
8 3
7 6

output:

11111111111111111111101111111111111111100111111101

result:

wrong answer 1st words differ - expected: '11111111111111111111111111111111111111111111111111', found: '11111111111111111111101111111111111111100111111101'