QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#512709 | #9170. Cycle Game | ucup-team052# | WA | 4ms | 79648kb | C++23 | 4.7kb | 2024-08-10 15:29:22 | 2024-08-10 15:29:22 |
Judging History
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'