QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288322 | #6398. Puzzle: Tapa | Slongod | WA | 1ms | 3532kb | C++14 | 4.3kb | 2023-12-22 15:04:39 | 2023-12-22 15:04:40 |
Judging History
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 (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: 100
Accepted
time: 0ms
memory: 3452kb
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: 3496kb
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: 3508kb
input:
2 2 2.2 ... 2.2
output:
YES 2.2 ### 2.2
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3468kb
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: 3520kb
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: 3500kb
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: 1ms
memory: 3532kb
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: 3528kb
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:
YES 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#...
result:
wrong answer Clue not satisfied at (5,1)