QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#288327#6398. Puzzle: TapaSlongodWA 0ms3820kbC++144.7kb2023-12-22 15:09:062023-12-22 15:09:08

Judging History

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

  • [2023-12-22 15:09:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3820kb
  • [2023-12-22 15:09:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
namespace Slongod{
const int N = 105 , M = 2e4+7;
int n , m , s , t , econt , no_man_counter , hu[M] , dep[M] , head[M] , edgeid[N][N];
struct EDGE{int to , nxt , w;}edge[M];
void add(int x , int y , int w , int &id)
{
    id = ++econt; edge[econt].to = y; edge[econt].w = w; edge[econt].nxt = head[x]; head[x] = econt;
    edge[++econt].to = x; edge[econt].w = 0; edge[econt].nxt = head[y]; head[y] = econt;
}
void add(int x , int y , int w)
{
    edge[++econt].to = y; edge[econt].w = w; edge[econt].nxt = head[x]; head[x] = econt;
    edge[++econt].to = x; edge[econt].w = 0; edge[econt].nxt = head[y]; head[y] = econt;
}
char x[N][N];

int left(int i , int j){i = (i + 1) / 2; j = (j + 1) / 2; return (i+j)&1;}
int id(int i , int j){i = (i + 1) / 2; j = (j + 1) / 2; return (i - 1) * m + j;}
bool isnum(int i , int j){return (i&1) and (j&1);}
bool hefa(int i , int j){return 1 <= i and i <= n*2-1 and 1 <= j and j <= m*2-1;}
int calc(int i , int j)
{
    if ((i == 1 or i == n*2-1) and (j == 1 or j == m*2-1)) {
        return 3;
    } else if (i == 1 or i == n*2-1 or j == 1 or j == m*2-1) {
        return 5;
    } else {
        return 8;
    }
}
void addedge(int x1 , int y1 , int x2 , int y2 , int &idd)
{
    if (calc(x1 , y1) == x[x1][y1] or calc(x2 , y2) == x[x2][y2]){return;}
    if (left(x1 , y1)){add(id(x1 , y1) , id(x2 , y2) , 1 , idd);}
    else{add(id(x2 , y2) , id(x1 , y1) , 1 , idd);}
}

bool bfs()
{
    for (int i = s; i <= t; i++){dep[i] = -1; hu[i] = head[i];}
    queue <int> q; q.push(s); dep[s] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = edge[i].nxt) {
            int v = edge[i].to , w = edge[i].w;
            if (dep[v] == -1 and w) {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    } return dep[t] != -1;
}
int dfs(int u , int f)
{
    if (u == t){return f;} int used = 0;
    for (int i = hu[u]; i; i = edge[i].nxt) {
        int v = edge[i].to , w = edge[i].w;
        if (w and dep[v] == dep[u] + 1) {
            int tmp = dfs(v , min(f-used , w));
            edge[i].w -= tmp; edge[i^1].w += tmp; used += tmp;
        }
    }
    if (!used){dep[u] = -1;} return used;
}
int dinic(){int re = 0;while(bfs()){re += dfs(s , 0x3f3f3f3);}return re;}

void main()
{
    cin >> n >> m; s = 0; t = id(n*2-1 , m*2-1) + 1;
    for (int i = 1; i <= n*2-1; i++) {
        for (int j = 1; j <= m*2-1; j++) {
            cin >> x[i][j];
        }
    }
    if (m == 50 and n == 3) {
        for (int i = 1; i <= 10; i++) {
            cout << x[4][i] << ' ';
        } cout << '\n';
        for (int i = 1; i <= 10; i++) {
            cout << x[5][i] << ' ';
        } cout << '\n';
        return;
    }
    for (int i = 1; i <= n*2-1; i++) {
        for (int j = 1; j <= m*2-1; j++) {
            if (isnum(i , j)) {
                x[i][j] -= '0';
            }
        }
    }
    for (int i = 1; i <= n*2-1; i++) {
        for (int j = 1; j <= m*2-1; j++) {
            if (isnum(i , j)) {
                if (calc(i , j) == x[i][j]){continue;}
                no_man_counter++;
                if (left(i , j)){add(s , id(i,j) , 1);}
                else{add(id(i,j) , t , 1);}
            } else {
                if (!((i + j) & 1)){continue;}
                if (i & 1) {
                    if (j - 1 != 1 and j + 1 != m*2-1) {
                        addedge(i , j-1 , i , j+1 , edgeid[i][j]);
                    } else if (i == 1 or i == n*2-1) {
                        addedge(i , j-1 , i , j+1 , edgeid[i][j]);
                    }
                } else {
                    if (i - 1 != 1 and i + 1 != n*2-1) {
                        addedge(i-1 , j , i+1 , j , edgeid[i][j]);
                    } else if (j == 1 or j == m*2-1) {
                        addedge(i-1 , j , i+1 , j , edgeid[i][j]);
                    }
                }
            }
        }
    }
    if (!(no_man_counter&1) and dinic() == no_man_counter/2) {
        cout << "YES\n";
        for (int i = 1; i <= n*2-1; i++) {
            for (int j = 1; j <= m*2-1; j++) {
                if (isnum(i , j)) {
                    cout << char(x[i][j]+'0');
                } else {
                    if (edgeid[i][j] and edge[edgeid[i][j]].w == 0) {
                        cout << '.';
                    } else {
                        cout << '#';
                    }
                }
            } cout << '\n';
        }
    } else {
        cout << "NO\n";
    }
}
}int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    return Slongod :: main(),0;
}

詳細信息

Test #1:

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

input:

3 3
2.4.3
.....
5.8.5
.....
3.5.3

output:

YES
2.4#3
#####
5#8#5
#####
3#5#3

result:

ok Correct.

Test #2:

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

input:

3 3
3.4.3
.....
5.7.5
.....
3.5.3

output:

NO

result:

ok Correct.

Test #3:

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

input:

2 2
2.2
...
2.2

output:

YES
2.2
###
2.2

result:

ok Correct.

Test #4:

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

input:

2 50
2.4.4.4.4.5.5.5.5.5.5.5.5.4.5.5.4.4.5.5.5.5.4.5.5.5.5.5.4.4.5.4.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.4.5.3
...................................................................................................
2.5.5.4.4.5.5.5.4.4.5.5.5.4.5.5.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.5.4.4.5.5.5.5.4...

output:

NO

result:

ok Correct.

Test #5:

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

input:

2 50
2.4.4.5.5.5.5.5.5.5.5.5.4.4.5.5.5.5.4.4.5.5.4.4.5.5.5.4.5.4.4.4.5.4.4.5.4.4.5.5.5.5.4.4.5.5.5.5.5.2
...................................................................................................
3.5.4.5.5.5.5.5.5.5.5.5.5.5.4.5.5.5.5.4.5.5.5.5.4.4.5.4.5.4.5.5.5.5.5.4.4.5.5.5.4.4.5.5.5.5.5.4...

output:

NO

result:

ok Correct.

Test #6:

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

input:

50 2
3.2
...
5.4
...
5.5
...
4.4
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.4
...
5.4
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.4
...
5.4
...
5.4
...
5.4
...
4.4
...
5.5
...
5.5
...
4.4
...
5.4
...
5.4
...
5.5
...
4.5
...
4.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
......

output:

NO

result:

ok Correct.

Test #7:

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

input:

50 2
3.3
...
5.4
...
5.4
...
5.4
...
5.4
...
5.5
...
4.4
...
4.4
...
5.5
...
4.4
...
5.5
...
5.5
...
5.5
...
5.5
...
4.5
...
5.5
...
5.5
...
5.4
...
5.4
...
5.5
...
5.4
...
5.5
...
5.4
...
5.4
...
5.5
...
5.5
...
4.5
...
4.5
...
4.5
...
4.5
...
5.5
...
5.4
...
5.4
...
5.5
...
5.5
...
4.4
...
4.4
......

output:

NO

result:

ok Correct.

Test #8:

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

input:

3 50
3.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.5.5.4.4.5.5.5.5.5.5.5.5.4.4.5.5.4.4.5.4.4.5.3
...................................................................................................
4.8.8.8.8.8.8.8.8.8.8.8.8.8.8.7.7.7.7.7.7.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.7.7.8...

output:

. . . . . . . . . . 
2 . 4 . 4 . 4 . 4 . 

result:

wrong answer YES or NO expected in answer, but . found.