QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#512709#9170. Cycle Gameucup-team052#WA 4ms79648kbC++234.7kb2024-08-10 15:29:222024-08-10 15:29:22

Judging History

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

  • [2024-08-10 15:29:22]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:79648kb
  • [2024-08-10 15:29:22]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;

const int N = 6e5 + 5;
const int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};

int sx[N], sy[N], w[N];
int n, m, k;

inline int s(int x, int y) {
	return (x - 1) * m + y;
}

pii edg[N];
int ch[N][2], rev[N], fa[N], st[N], mn[N], pos[N], val[N], rub[N];
int tot, top, len;

inline int newNode() {
	if (len) return rub[len--];
	return ++tot;
}

void update(int u) {
	mn[u] = val[u]; pos[u] = u;
	for (int i = 0; i <= 1; i++) {
		if (ch[u][i] && mn[ch[u][i]] < mn[u]) {
			mn[u] = mn[ch[u][i]];
			pos[u] = pos[ch[u][i]];
		}
	}
}

inline int isroot(int u) {
	return ch[fa[u]][0] != u && ch[fa[u]][1] != u;
}

inline int get(int u) {
	return ch[fa[u]][1] == u;
}

void add_rev(int u) {
	rev[u] ^= 1;
	swap(ch[u][0], ch[u][1]);
}

void pushdown(int u) {
	if (rev[u]) {
		if (ch[u][0]) add_rev(ch[u][0]);
		if (ch[u][1]) add_rev(ch[u][1]);
		rev[u] = 0;
	}
}

void rotate(int u) {
    int old = fa[u], oldd = fa[old], k = get(u);
    if (!isroot(old)) { ch[oldd][get(old)] = u; } fa[u] = oldd;
    ch[old][k] = ch[u][k ^ 1]; fa[ch[u][k ^ 1]] = old;
    fa[old] = u; ch[u][k ^ 1] = old;
    update(old); update(u);
}

void splay(int u) {
    st[top = 1] = u;
    for (int i = u; !isroot(i); i = fa[i]) st[++top] = fa[i];
    for (int i = top; i >= 1; i--) pushdown(st[i]);
    for (; !isroot(u); rotate(u)) if (!isroot(fa[u])) rotate(get(u) == get(fa[u]) ? fa[u] : u);
}

void access(int u) {
    for (int i = 0; u; i = u, u = fa[u]) {
        splay(u);
        ch[u][1] = i;
        update(u);
    }
}

void makeroot(int u) {
    access(u);
    splay(u);
    add_rev(u);
}

void link(int u, int v) {
	// fprintf(stderr, "link %d %d\n", u, v);
    makeroot(u);
    fa[u] = v;
}

void cut(int u, int v) {
	// fprintf(stderr, "cut %d %d\n", u, v);
    makeroot(u);
    access(v);
    splay(v);
    fa[u] = ch[v][0] = 0;
    update(v);
}

pii query(int u, int v) {
    makeroot(u);
    access(v);
    splay(v);
    return make_pair(mn[v], pos[v]);
}

struct edge {
	int u, v, w;
	edge (int a = 0, int b = 0, int c = 0) : u(a), v(b), w(c) {}
	bool operator < (const edge A) const { return w > A.w; }
} e[N * 8];

int f[N], elen;

int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n * m; i++) w[i] = k;
	for (int i = 1; i <= k; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		sx[i] = x; sy[i] = y;
		w[s(x, y)] = min(w[s(x, y)], i - 1);
	}
	for (int i = 1; i <= n * m + 1; i++) f[i] = i;
	tot = n * m + 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int u = s(i, j), ok = 0;
			for (int d = 0; d < 8; d++) {
				int x = i + dx[d];
				int y = j + dy[d];
				if (x < 1 || y < 1 || x > n || y > m) {
					ok = 1;
				} else {
					int v = s(x, y);
					if (u < v) {
						e[++elen] = edge(u, v, min(w[u], w[v]));
					}
				}
			}
			if (ok) {
				e[++elen] = edge(n * m + 1, u, w[u]);
			}
		}
	}
	for (int i = 1; i <= n * m + 1; i++) {
		mn[i] = val[i] = 1e9;
		pos[i] = i;
	}
	sort(e + 1, e + elen + 1);
	for (int i = 1; i <= elen; i++) {
		int x = find(e[i].u), y = find(e[i].v);
		if (x != y) {
			f[x] = y;
			int tmp = newNode();
			edg[tmp] = make_pair(e[i].u, e[i].v);
			mn[tmp] = val[tmp] = e[i].w; pos[tmp] = tmp;
			link(e[i].u, tmp);
			link(e[i].v, tmp);
		}
	}
	for (int i = 1; i <= k; i++) {
		int ans = 1;
		for (int d = 0; d < 8; d++) {
			int x = sx[i] + dx[d];
			int y = sy[i] + dy[d];
			if (x >= 1 && y >= 1 && x <= n && y <= m && w[s(x, y)] >= i) {
				// fprintf(stderr, "i = %d, x = %d, y = %d, val = %d\n", i, x, y, query(s(x, y), n * m + 1).first);
				if (query(s(x, y), n * m + 1).first == i - 1) {
					ans = 0;
					break;
				}
			}
		}
		printf("%d", ans);
		if (!ans) {
			int u = s(sx[i], sy[i]);
			w[u] = k;
			int ok = 0;
			for (int d = 0; d < 8; d++) {
				int x = sx[i] + dx[d];
				int y = sy[i] + dy[d];
				if (x >= 1 && y >= 1 && x <= n && y <= m) {
					if (w[s(x, y)] >= i) {
						int v = s(x, y);
						pii t = query(u, v);
						if (t.first < w[v]) {
							int pos = t.second;
							cut(pos, edg[pos].first);
							cut(pos, edg[pos].second);
							edg[pos] = make_pair(u, v);
							val[pos] = w[v];
							link(u, pos); link(v, pos);
						}
					}
				} else ok = 1;
			}
			if (ok) {
				int v = n * m + 1;
				pii t = query(u, v);
				if (t.first < k) {
					int pos = t.second;
					cut(pos, edg[pos].first);
					cut(pos, edg[pos].second);
					edg[pos] = make_pair(u, v);
					val[pos] = k;
					link(u, pos); link(v, pos);
				}
			}
		}
	}
	printf("\n");
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 77620kb

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: 4ms
memory: 79596kb

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: 77608kb

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: 0
Accepted
time: 4ms
memory: 77608kb

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:

11111111111111111111111111111111111111111111111111

result:

ok "11111111111111111111111111111111111111111111111111"

Test #5:

score: 0
Accepted
time: 4ms
memory: 79580kb

input:

3 5 11
1 5
2 4
1 2
1 3
3 3
3 1
3 4
2 3
1 4
2 1
2 5

output:

11111111111

result:

ok "11111111111"

Test #6:

score: 0
Accepted
time: 4ms
memory: 79544kb

input:

7 9 12
7 3
2 3
6 2
2 2
4 2
2 8
5 7
4 4
6 8
2 7
7 2
1 9

output:

111111111111

result:

ok "111111111111"

Test #7:

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

input:

1 4 1
1 2

output:

1

result:

ok "1"

Test #8:

score: -100
Wrong Answer
time: 4ms
memory: 79648kb

input:

9 8 67
5 5
8 3
9 5
7 4
5 1
9 3
4 2
2 5
1 7
7 8
7 2
8 5
6 1
8 8
4 4
5 4
1 5
3 4
6 7
2 3
3 7
5 7
2 4
2 7
1 3
7 3
2 8
6 6
6 2
6 3
7 5
9 6
7 6
3 6
1 1
6 4
3 1
5 3
8 7
2 1
4 1
8 4
8 6
3 5
5 8
1 6
1 2
4 6
9 4
1 4
3 3
4 8
8 1
4 7
9 8
3 8
6 5
6 8
3 2
2 2
7 1
9 2
4 3
1 8
4 5
8 2
7 7

output:

1111111111111111111111111111111111111111111110011111101010001101111

result:

wrong answer 1st words differ - expected: '111111111111111111111111111111...1111111110010101101000101101101', found: '111111111111111111111111111111...1111111110011111101010001101111'