QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#328557#833. Cells BlockingEasonLiangAC ✓415ms57356kbC++143.0kb2024-02-15 21:08:292024-02-15 21:08:29

Judging History

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

  • [2024-02-15 21:08:29]
  • 评测
  • 测评结果:AC
  • 用时:415ms
  • 内存:57356kb
  • [2024-02-15 21:08:29]
  • 提交

answer

#include <bits/stdc++.h>
#define FileIO_(file) \
    freopen (file ".in", "r", stdin); \
    freopen (file ".out", "w", stdout);

using namespace std;

template<typename Tp>
inline void chmin (Tp &x, const Tp &y) { if (y < x) x = y; }
template<typename Tp>
inline void chmax (Tp &x, const Tp &y) { if (x < y) x = y; }

typedef double dbl;
typedef long long ll;
typedef long double ldb;

void init () {}

const int maxnm = 3e3 + 20;
int n, m, len, g[maxnm][maxnm];
ll cnt, num, ans;
bool chpre[maxnm][maxnm], chsuf[maxnm][maxnm];

int getid (int x, int y) {
    return (x - 1) * m + (y - 1);
}

vector<int> findrd (int sx, int sy, int dx, int dy) {
    vector<int> res (1, getid (sx, sy));

    while (getid (sx, sy) != n * m - 1) {
        int flag = !chpre[sx + dx][sy + dy];
        res.emplace_back (getid (
            sx += dx ^ flag, sy += dy ^ flag));
    }

    return res;
}

int check (const vector<int> &lhs, const vector<int> &rhs) {
    int res = 0;
    for (int i = 0; i < len; ++i)
        res += lhs[i] == rhs[i];
    return res;
}

void solve () {
    scanf ("%d%d", &n, &m); len = n + m - 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            while (!isgraph (g[i][j] = getchar ()));
            cnt += g[i][j] = g[i][j] == '.';
        }
    }

    if (!g[1][1] || !g[n][m]) {
        printf ("%lld\n", cnt * (cnt - 1) / 2);
        return;
    }

    chpre[n][m] = chsuf[1][1] = 1;

    for (int i = n; i; --i) {
        for (int j = m; j; --j) {
            if (i != n || j != m)
                chpre[i][j] = g[i][j] &&
                    (chpre[i + 1][j] || chpre[i][j + 1]);
        }
    }

    if (!chpre[1][1]) {
        printf ("%lld\n", cnt * (cnt - 1) / 2);
        return;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i != 1 || j != 1)
                chsuf[i][j] = g[i][j] &&
                    (chsuf[i - 1][j] || chsuf[i][j - 1]);
        }
    }

    vector<int> lrd = findrd (1, 1, 1, 0);
    vector<int> rrd = findrd (1, 1, 0, 1);

    num = check (lrd, rrd);
    ans += num * (cnt - 1) - num * (num - 1) / 2;

    for (int i = 0; i < len; ++i) {
        if (lrd[i] == rrd[i]) continue;
        int x = lrd[i] / m + 1, y = lrd[i] % m + 1;
        do --x, ++y; while (!chpre[x][y] || !chsuf[x][y]);
        vector<int> nrd; int nx = x, ny = y;
        while (getid (nx, ny)) {
            int flag = chsuf[nx][ny - 1];
            nrd.emplace_back (getid (
                nx -= !flag, ny -= flag));
        }
        reverse (nrd.begin (), nrd.end ());
        for (int pos : findrd (x, y, 1, 0))
            nrd.emplace_back (pos);
        // for (int pos : nrd)
        //     cerr << pos << " ";
        // cerr << endl;
        ans += check (nrd, rrd) - num;
    }

    printf ("%lld\n", ans);
}

int main () {
//	#ifndef LSY
//	FileIO_("");
//	#endif
    int t = 1; init ();
//	scanf ("%d", &t);
    while (t--) solve ();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3
...
...
...

output:

17

result:

ok 1 number(s): "17"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5848kb

input:

3 3
.**
.*.
...

output:

15

result:

ok 1 number(s): "15"

Test #3:

score: 0
Accepted
time: 1ms
memory: 6104kb

input:

3 4
****
....
****

output:

6

result:

ok 1 number(s): "6"

Test #4:

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

input:

5 5
*....
.*.*.
*****
*.***
..*..

output:

66

result:

ok 1 number(s): "66"

Test #5:

score: 0
Accepted
time: 1ms
memory: 5904kb

input:

10 10
...***.*..
**...*.***
...***.*..
.**...*.*.
.*****..*.
..*.****.*
.**...****
..*..*.*.*
*.*.**....
....**...*

output:

1378

result:

ok 1 number(s): "1378"

Test #6:

score: 0
Accepted
time: 354ms
memory: 56964kb

input:

3000 3000
.....................................................................................................................................................................................................................................................................................................

output:

17999999

result:

ok 1 number(s): "17999999"

Test #7:

score: 0
Accepted
time: 352ms
memory: 57064kb

input:

3000 3000
...................................................................................................................*......................................................................................................................................................................*..........

output:

17981671

result:

ok 1 number(s): "17981671"

Test #8:

score: 0
Accepted
time: 355ms
memory: 57060kb

input:

3000 3000
.....................................................................................................................................................................................................................................................................................................

output:

17963615

result:

ok 1 number(s): "17963615"

Test #9:

score: 0
Accepted
time: 359ms
memory: 57336kb

input:

3000 3000
.........................................................................................................*...........................................................................................................................................................................................

output:

17945165

result:

ok 1 number(s): "17945165"

Test #10:

score: 0
Accepted
time: 351ms
memory: 57356kb

input:

3000 3000
......................................................................................................................................*........................................................................................................................................*.....................

output:

17928211

result:

ok 1 number(s): "17928211"

Test #11:

score: 0
Accepted
time: 354ms
memory: 57332kb

input:

3000 3000
...........................................*.........................................................................................................................................................................................................................................................

output:

17911522

result:

ok 1 number(s): "17911522"

Test #12:

score: 0
Accepted
time: 363ms
memory: 57332kb

input:

3000 3000
..............................*................................................................................................................*.....................................................................................................................................................

output:

17892283

result:

ok 1 number(s): "17892283"

Test #13:

score: 0
Accepted
time: 362ms
memory: 57024kb

input:

3000 3000
................................................................*....*................................................................................................................................................................................*..............................................

output:

17873837

result:

ok 1 number(s): "17873837"

Test #14:

score: 0
Accepted
time: 359ms
memory: 57076kb

input:

3000 3000
............................................................................................*.............................................................................*.....................................................................................................*....................

output:

17856701

result:

ok 1 number(s): "17856701"

Test #15:

score: 0
Accepted
time: 349ms
memory: 57068kb

input:

3000 3000
......................................*..........................................................................................................................................................*...................................................................................................

output:

17837857

result:

ok 1 number(s): "17837857"

Test #16:

score: 0
Accepted
time: 364ms
memory: 57328kb

input:

3000 3000
.................................................................................................................................................................................................................................*...................................................................

output:

17819731

result:

ok 1 number(s): "17819731"

Test #17:

score: 0
Accepted
time: 383ms
memory: 57076kb

input:

3000 3000
......**.....*.......*.*..........*..*...............**.............*.......*......*........*...*.....*.*.................*......*....*.........*....................*.................*.......................*.......*..*.*.......*.......................*..........*..*......................*...

output:

16202000

result:

ok 1 number(s): "16202000"

Test #18:

score: 0
Accepted
time: 415ms
memory: 57088kb

input:

3000 3000
..................*....*....*...*.*.............*.............*....*.*..*...*...*...*....*.................*...*.*.***...*....*......*.......**...*.......*.*...**...*...*...**.........*..........*.....*.*....*..*.......*.........*..*.....*...............**.......*.....*.*..*.*.*........*.....

output:

21600132

result:

ok 1 number(s): "21600132"

Test #19:

score: 0
Accepted
time: 67ms
memory: 48092kb

input:

3000 3000
..*.**...*...............*........*.*..*.*.....*........*.*..........***..*..*..*..*.*....*...*.*.....***.*...*........*..*.****..*.*....**.......*......*....*..*......*......*..*..*.*..*....*..**.*.......**.*...*....**.....**..*......*...*....*..*.**.*..***...*.....*....***.*........*.......

output:

19862779430431

result:

ok 1 number(s): "19862779430431"

Test #20:

score: 0
Accepted
time: 67ms
memory: 48096kb

input:

3000 3000
.**.**..***....*.*....*..*...*.**.**.**.......*...*........*.**.*...*...**..*...*.*.**.*.*.*.*..*...*.....*.*.**.*.*....*.**.....*..**.**.*....**.**.**..*..**...*...***.**.*.*......**.**.*...****.....***.*..*.**.*......*..**.**.**.....**...*.*..***.******...**....****..***..**.*........*.....

output:

14601805246666

result:

ok 1 number(s): "14601805246666"

Test #21:

score: 0
Accepted
time: 1ms
memory: 6116kb

input:

1 1
*

output:

0

result:

ok 1 number(s): "0"

Test #22:

score: 0
Accepted
time: 1ms
memory: 5840kb

input:

1 1
.

output:

0

result:

ok 1 number(s): "0"

Test #23:

score: 0
Accepted
time: 1ms
memory: 5844kb

input:

2 2
..
..

output:

6

result:

ok 1 number(s): "6"

Test #24:

score: 0
Accepted
time: 27ms
memory: 40100kb

input:

3000 3000
.***..**..*.*.*..*...**.*.**...***.....*..***.***.***.*..***.*......*.**.***.***.*...**.*.*..***.*..*.**..***.....*.*...***.*.***.*...*.*.....***.*..**...*.*..*.******.*.*...**.*..**.**.**.*.**..***.**.***..*......**.***.**.*....*..*.....*...*..*.*..*..*.*...**.**...*..**..***.**..*....*.....

output:

10151159625145

result:

ok 1 number(s): "10151159625145"

Test #25:

score: 0
Accepted
time: 25ms
memory: 40284kb

input:

3000 3000
*******************************************************************************************************************************************************************************************************************************************************.******************************************...

output:

39716328

result:

ok 1 number(s): "39716328"

Test #26:

score: 0
Accepted
time: 352ms
memory: 57344kb

input:

3000 3000
..*..................................................................................................................................................................................................................................................................................................

output:

35988321

result:

ok 1 number(s): "35988321"

Test #27:

score: 0
Accepted
time: 364ms
memory: 57024kb

input:

3000 3000
.....................................................................................................................................................................................................................................................................................................

output:

35981866

result:

ok 1 number(s): "35981866"

Test #28:

score: 0
Accepted
time: 350ms
memory: 57064kb

input:

3000 3000
...**................................................................................................................................................................................................................................................................................................

output:

17988153

result:

ok 1 number(s): "17988153"

Test #29:

score: 0
Accepted
time: 347ms
memory: 57076kb

input:

3000 3000
...*.*...............................................................................................................................................................................................................................................................................................

output:

35969654

result:

ok 1 number(s): "35969654"

Test #30:

score: 0
Accepted
time: 333ms
memory: 57076kb

input:

3000 3000
..*..................................................................................................................................................................................................................................................................................................

output:

17982216

result:

ok 1 number(s): "17982216"

Test #31:

score: 0
Accepted
time: 352ms
memory: 57064kb

input:

3000 3000
....**.*.............................................................................................................................................................................................................................................................................................

output:

71916090

result:

ok 1 number(s): "71916090"

Test #32:

score: 0
Accepted
time: 360ms
memory: 57060kb

input:

3000 3000
....****.............................................................................................................................................................................................................................................................................................

output:

71903186

result:

ok 1 number(s): "71903186"

Test #33:

score: 0
Accepted
time: 363ms
memory: 57056kb

input:

3000 3000
.........*...........................................................................................................................................................................................................................................................................................

output:

17973051

result:

ok 1 number(s): "17973051"

Test #34:

score: 0
Accepted
time: 344ms
memory: 57024kb

input:

3000 3000
.*.......*.............................................................................................................*................................................................................*............................................................................................

output:

35630636

result:

ok 1 number(s): "35630636"

Test #35:

score: 0
Accepted
time: 338ms
memory: 57072kb

input:

3000 3000
.**...........................*..........................................................................................................................................*...........................................................................................................................

output:

44529907

result:

ok 1 number(s): "44529907"

Test #36:

score: 0
Accepted
time: 341ms
memory: 57064kb

input:

3000 3000
....*................................................................................................................................................................................................................................................................................................

output:

53426863

result:

ok 1 number(s): "53426863"

Test #37:

score: 0
Accepted
time: 353ms
memory: 57296kb

input:

3000 3000
..*.*........................................................................*............................*...............*.............................................................................................................................................*........*...................

output:

53419301

result:

ok 1 number(s): "53419301"

Test #38:

score: 0
Accepted
time: 359ms
memory: 57072kb

input:

3000 3000
......*.........*...................................................................................*.....................................................................................................................*................................................*.........................

output:

26705269

result:

ok 1 number(s): "26705269"

Test #39:

score: 0
Accepted
time: 370ms
memory: 57012kb

input:

3000 3000
....*.**....*................*............................*..........*...............................................................................................................................................................................................................................

output:

17799069

result:

ok 1 number(s): "17799069"

Test #40:

score: 0
Accepted
time: 341ms
memory: 57052kb

input:

3000 3000
...***.......................................*...........*.....................*........*...........................................................................................................................................................*................................................

output:

53393629

result:

ok 1 number(s): "53393629"

Test #41:

score: 0
Accepted
time: 341ms
memory: 57052kb

input:

3000 3000
.....................................................................................................................................................................................................................................................................................................

output:

98852811

result:

ok 1 number(s): "98852811"

Test #42:

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

input:

1 3000
........................................................................................................................................................................................................................................................................................................

output:

4498500

result:

ok 1 number(s): "4498500"

Test #43:

score: 0
Accepted
time: 326ms
memory: 57332kb

input:

3000 3000
.*.....*...........................................................................................................*...................................*........................................................................................*............*.......................................

output:

88979547

result:

ok 1 number(s): "88979547"

Test #44:

score: 0
Accepted
time: 344ms
memory: 57072kb

input:

3000 3000
.....................................................................................................................................................................................................................................................................................................

output:

35964327

result:

ok 1 number(s): "35964327"