QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#549735#9170. Cycle Gameucup-team3519#WA 1ms5924kbC++232.2kb2024-09-06 20:45:392024-09-06 20:45:39

Judging History

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

  • [2024-09-06 20:45:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5924kb
  • [2024-09-06 20:45:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define V vector
#define pb push_back
#define fi first
#define se second
#define all1(x) (x).begin() + 1, (x).end()
typedef pair<int, int> pi;
const int MN = 6e5 + 10;

int f[MN], siz[MN];
int par(int x){
    if(x == f[x]) return x;
    return f[x] = par(f[x]);
}
void mer(int a, int b){
    a=par(a), b = par(b);
    if(a == b) return;
    f[a] = b;
    siz[b] += siz[a];
}
void ini(int n){
    for(int i = 1; i <= n; i++) f[i] = i, siz[i] = 1;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    int m, k; cin >> m >> k;
    ini(n * m * 2);
    auto id = [&](int x, int y, int type) -> int {
        return (x - 1) * m + y + type * n * m;
    };

    auto out = [&](int x, int y) -> bool {
        return x < 1 || y < 1 || x > n || y > m;
    };

    auto near = [&](int x, int y, int x2, int y2) -> bool {
        return (x == x2 && abs(y - y2) == 1) || (y == y2 && abs(x - x2) == 1);
    };

    V<V<int>> hav(n + 1, V<int>(m + 1));

    for(int i = 1; i <= k; i++) {
        int x, y; cin >> x >> y;
        bool ok = 1;
        V<pi> blk;
        for(int dx = -1; dx <= 1; dx++) {
            for(int dy = -1; dy <= 1; dy++) {
                if(out(x + dx, y + dy)) continue;
                f[id(x + dx, y + dy, 1)] = id(x + dx, y + dy, 1);
                if(hav[x + dx][y + dy]) blk.pb({x + dx, y + dy});
            }
        }
        for(auto p1 : blk) {
            for(auto p2 : blk) {
                if(near(p1.fi, p1.se, p2.fi, p2.se)) mer(id(p1.fi, p1.se, 1), id(p2.fi, p2.se, 1));
            }
        }
        for(auto p1 : blk) for(auto p2 : blk) {
            if(near(p1.fi, p1.se, x, y) && near(p2.fi, p2.se, x, y) && 
                par(id(p1.fi, p1.se, 0)) == par(id(p2.fi, p2.se, 0)) && par(id(p1.fi, p1.se, 1)) != par(id(p2.fi, p2.se, 1))) ok = 0;
        }
        if(ok) {
            hav[x][y] = 1;
            for(auto p : blk) {
                if(near(p.fi, p.se, x, y)) {
                    mer(id(p.fi, p.se, 0), id(x, y, 0));
                }
            }
            cout << 1;
        } else cout << 0;
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5660kb

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: 1ms
memory: 5664kb

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: 1ms
memory: 5664kb

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: 1ms
memory: 5924kb

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: 1ms
memory: 5604kb

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: 1ms
memory: 5604kb

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: 1ms
memory: 5604kb

input:

1 4 1
1 2

output:

1

result:

ok "1"

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 5644kb

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'