oj.uz

Submission #922274

# Submission time Handle Problem Language Result Execution time Memory
922274 2024-02-05T10:51:40 Z ttamx Raspad (COI17_raspad) C++14
100 / 100
 390 ms 227568 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=100005;
const int M=55;

int n,m;
string s[N];
long long ans;
bool vis[N][M];

pair<int,int> dfs(int i,int j){
    if(j==0||j==m-1)return {0,n-1};
    pair<int,int> res(i,i);
    vis[i][j]=true;
    for(int di=-1;di<=1;di++)for(int dj=-1;dj<=1;dj++){
        int ni=i+di,nj=j+dj;
        if(0<=ni&&ni<n&&0<=nj&&nj<m&&!vis[ni][nj]&&s[ni][nj]=='0'){
            auto [x,y]=dfs(ni,nj);
            res.first=min(res.first,x);
            res.second=max(res.second,y);
        }
    }
    return res;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0;i<n;i++)cin >> s[i];
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(s[i][j]=='1')ans+=1LL*(i+1)*(n-i);
    for(int i=1;i<n;i++)for(int j=0;j<m;j++)if(s[i][j]=='1'&&s[i-1][j]=='1')ans-=1LL*i*(n-i);
    for(int i=0;i<n;i++)for(int j=1;j<m;j++)if(s[i][j]=='1'&&s[i][j-1]=='1')ans-=1LL*(i+1)*(n-i);
    for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(s[i][j]=='1'&&s[i][j-1]=='1'&&s[i-1][j]=='1'&&s[i-1][j-1]=='1')ans+=1LL*i*(n-i);
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(s[i][j]=='0'&&!vis[i][j]){
        auto [x,y]=dfs(i,j);
        ans+=1LL*x*(n-y-1);
    }
    cout << ans;
}

Compilation message

raspad.cpp: In function 'std::pair<int, int> dfs(int, int)':
raspad.cpp:20:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |             auto [x,y]=dfs(ni,nj);
      |                  ^
raspad.cpp: In function 'int main()':
raspad.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |         auto [x,y]=dfs(i,j);
      |              ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 5 ms 7260 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 4 ms 5980 KB Output is correct
12 Correct 2 ms 4760 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4700 KB Output is correct
2 Correct 108 ms 28280 KB Output is correct
3 Correct 75 ms 10432 KB Output is correct
4 Correct 65 ms 60884 KB Output is correct
5 Correct 28 ms 6996 KB Output is correct
6 Correct 82 ms 10580 KB Output is correct
7 Correct 37 ms 10284 KB Output is correct
8 Correct 41 ms 10068 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 5 ms 7260 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 4 ms 5980 KB Output is correct
12 Correct 2 ms 4760 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct
14 Correct 11 ms 4700 KB Output is correct
15 Correct 108 ms 28280 KB Output is correct
16 Correct 75 ms 10432 KB Output is correct
17 Correct 65 ms 60884 KB Output is correct
18 Correct 28 ms 6996 KB Output is correct
19 Correct 82 ms 10580 KB Output is correct
20 Correct 37 ms 10284 KB Output is correct
21 Correct 41 ms 10068 KB Output is correct
22 Correct 271 ms 125748 KB Output is correct
23 Correct 220 ms 20308 KB Output is correct
24 Correct 152 ms 20036 KB Output is correct
25 Correct 370 ms 227568 KB Output is correct
26 Correct 148 ms 29604 KB Output is correct
27 Correct 214 ms 22056 KB Output is correct
28 Correct 196 ms 19060 KB Output is correct
29 Correct 390 ms 163768 KB Output is correct
30 Correct 143 ms 29640 KB Output is correct
31 Correct 159 ms 38996 KB Output is correct
32 Correct 111 ms 20316 KB Output is correct
33 Correct 143 ms 18940 KB Output is correct
34 Correct 212 ms 19636 KB Output is correct