Submission #631574

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
631574	2022-08-18T08:56:30 Z	GudStonks	Dijamant (COCI22_dijamant)	C++17	70 / 70	861 ms	15628 KB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, ans;
string s[2005];
queue<pair<int, int> >q;
bool us[2005][2005];
pair<int, int>dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
void fun()
{
    cin>>n>>m;
    for(int i = 0; i < n; i++)
    {
        cin>>s[i];
    }
    for(int i = 1; i < n - 1; i++)
    {
        for(int j = 1; j < m - 1; j++)
        {
            if(!us[i][j] && s[i][j] == '.')
            {
                vector<int>xx(n + 1, 0), yy(m + 1, 0);
                q.push({i, j});
                bool boo = 0;
                int c = 0;
                while(!q.empty())
                {
                    int x = q.front().first, 
                        y = q.front().second;
                    q.pop();
                    us[x][y] = 1;
                    bool goo = 0;
                    for(int k = 0; k < 4; k++)
                    {
                        if(x + dir[k].first > n - 1 
                            || x + dir[k].first < 0 
                            || y + dir[k].second > m - 1 
                            || y + dir[k].second < 0)
                        {
                            boo = 1;
                            continue;
                        }
                        if(s[x + dir[k].first][y + dir[k].second] == '#')
                            goo = 1;
                        else if(!us[x + dir[k].first][y + dir[k].second] &&
                                s[x + dir[k].first][y + dir[k].second] == '.')
                            q.push({x + dir[k].first, y + dir[k].second}),
                            us[x + dir[k].first][y + dir[k].second] = 1;
                    }
                    if(goo)
                        xx[x] += 10000 + y, yy[y] += 10000 + x, c++;
                }
                if(boo)
                    continue;
                if(c == 1)
                {
                    ans++;
                    continue;
                }
                int l = 0, x1, x2, y1, y2;
                while(l < n - 1 && xx[l] / 10000 == 0)
                    l++;
                if(xx[l] / 10000 != 1 || xx[l + 1] / 10000 != 2)
                    continue;
                x1 = xx[l];
                l++;
                int tt = 0;
                while(l < n - 1 && xx[l] / 10000 == 2)
                    l++, tt++;
                if(xx[l] / 10000 != 1 || (l != n - 1 && xx[l + 1] / 10000 != 0))
                    continue;
                x2 = xx[l];
                l = 0;
                while(l < m - 1 && yy[l] / 10000 == 0)
                    l++;
                if(yy[l] / 10000 != 1 || yy[l + 1] / 10000 != 2)
                    continue;
                y1 = yy[l];
                l++;
                while(l < m - 1 && yy[l] / 10000 == 2)
                    l++;
                if(yy[l] / 10000 != 1 || (l != m - 1 && yy[l + 1] / 10000 != 0) || tt % 2 == 0)
                    continue;
                y2 = yy[l];
                if((x1 % 10000) != (x2 % 10000) || (y1 % 10000) != (y2 % 10000))
                    continue;
                ans++;
            }
        }
    }
    cout<<ans;
}

int main()
{
	ll ttt = 1;
	//cin>>ttt;
	while(ttt--)
		fun();
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	496 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	508 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	496 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	508 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	167 ms	11260 KB	Output is correct
15	Correct	81 ms	11020 KB	Output is correct
16	Correct	384 ms	10908 KB	Output is correct
17	Correct	175 ms	11132 KB	Output is correct
18	Correct	279 ms	15628 KB	Output is correct
19	Correct	155 ms	10828 KB	Output is correct
20	Correct	181 ms	15620 KB	Output is correct
21	Correct	158 ms	10632 KB	Output is correct
22	Correct	258 ms	11424 KB	Output is correct
23	Correct	207 ms	10616 KB	Output is correct
24	Correct	238 ms	11536 KB	Output is correct
25	Correct	167 ms	10712 KB	Output is correct
26	Correct	861 ms	10864 KB	Output is correct