QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#372258 | #8507. Clever Cell Choices | YeongTree | WA | 2ms | 8600kb | C++17 | 3.1kb | 2024-03-31 08:00:09 | 2024-03-31 08:00:11 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <set>
#include <map>
#include <random>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii array<int, 3>
#define tiiii array<int, 4>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
typedef long long ll;
const int INF = (int)1e9 + 7;
using namespace std;
int N = 0, M = 0;
vector<int> gph[101010];
vector<int> rgph[101010];
int A[101010];
int B[101010];
int D[101010];
int pt[101010];
bool dfs(int x)
{
for(; pt[x] < (int)gph[x].size(); ++pt[x])
{
int y = gph[x][pt[x]];
if(B[y] == -1 || (D[x] + 1 == D[B[y]] && dfs(B[y])))
{
A[x] = y;
B[y] = x;
return true;
}
}
return false;
}
bool bfs(void)
{
fill(D, D + N, -1);
fill(pt, pt + N, 0);
queue<int> Q;
for(int i = 0; i < N; ++i) if(A[i] == -1) D[i] = 0, Q.push(i);
bool ret = false;
while(Q.size())
{
int x = Q.front(); Q.pop();
for(auto y : gph[x])
{
if(B[y] == -1) return true;
else if(D[B[y]] == -1) D[B[y]] = D[x] + 1, Q.push(B[y]);
}
}
return false;
}
int match()
{
int ret = 0;
while(bfs()) for(int i = 0; i < N; ++i) if(A[i] == -1 && dfs(i)) ++ret;
return ret;
}
int pA[101010];
int pB[101010];
int solA(int x)
{
if(pA[x] != -1) return pA[x];
pA[x] = 0;
for(auto y : rgph[A[x]]) if(solA(y)) return pA[x] = 1;
return pA[x] = 0;
}
int solB(int x)
{
if(pB[x] != -1) return pB[x];
pB[x] = 0;
for(auto y : gph[B[x]]) if(solB(y)) return pB[x] = 1;
return pB[x] = 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
string str[n];
for(auto &i : str) cin >> i;
int chc[n][m];
fill(*chc, *chc + n * m, -1);
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j) if(str[i][j] == '.')
{
if(i + j & 1) chc[i][j] = N++;
else chc[i][j] = M++;
}
}
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j) if(str[i][j] == '.')
{
if(i + j & 1)
{
for(int t = 0; t < 4; ++t)
{
int dx = i + "0211"[t] - '1';
int dy = j + "1102"[t] - '1';
if(dx >= 0 && dy >= 0 && dx < n && dy < m && str[dx][dy] == '.')
{
gph[chc[i][j]].push_back(chc[dx][dy]);
rgph[chc[dx][dy]].push_back(chc[i][j]);
}
}
}
}
}
// cout << "ok" << endl;
fill(A, A + N, -1);
fill(B, B + M, -1);
match();
// cout << "ok" << endl;
// cout << N << ' ' << M << '\n';
// for(int i = 0; i < N; ++i) cout << A[i] << ' '; cout << '\n';
// for(int i = 0; i < M; ++i) cout << B[i] << ' '; cout << '\n';
fill(pA, pA + N, -1);
fill(pB, pB + M, -1);
for(int i = 0; i < N; ++i) if(A[i] == -1) pA[i] = 1;
for(int i = 0; i < M; ++i) if(B[i] == -1) pB[i] = 1;
for(int i = 0; i < N; ++i) if(pA[i] == -1) solA(i);
for(int i = 0; i < M; ++i) if(pB[i] == -1) solB(i);
int ans = 0;
for(int i = 0; i < N; ++i) if(pA[i] == 1) ++ans;
for(int i = 0; i < M; ++i) if(pB[i] == 1) ++ans;
cout << ans;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8260kb
input:
3 3 #.# ... #.#
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 8584kb
input:
3 3 ..# ... ...
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 2ms
memory: 8252kb
input:
1 4 ...#
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 8316kb
input:
1 5 ####.
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 8360kb
input:
1 6 #..###
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 8584kb
input:
2 5 ....# ###.#
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 2ms
memory: 8304kb
input:
2 6 ...##. .#.###
output:
4
result:
ok 1 number(s): "4"
Test #8:
score: 0
Accepted
time: 2ms
memory: 8600kb
input:
5 5 ##... ##.#. ##.## ##.#. .##..
output:
7
result:
ok 1 number(s): "7"
Test #9:
score: 0
Accepted
time: 2ms
memory: 8288kb
input:
6 6 ...##. #..#.. ...... ..#... #...## .#....
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 8580kb
input:
10 10 ####.#...# .#.###.... #....#..#. .....#.#.. ##.#..#.#. ..#..##... .##.#####. #######.## .#.#.##..# .#.###.##.
output:
23
result:
wrong answer 1st numbers differ - expected: '26', found: '23'