QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288325#6398. Puzzle: TapaSlongodWA 0ms3428kbC++144.7kb2023-12-22 15:08:362023-12-22 15:08:37

Judging History

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

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

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3428kb

input:

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

output:


result:

wrong output format Unexpected end of file - token expected