oj.uz

Submission #940064

# Submission time Handle Problem Language Result Execution time Memory
940064 2024-03-07T04:56:00 Z VKnight Tracks in the Snow (BOI13_tracks) C++17
29.5833 / 100
 1065 ms 47660 KB 
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define gett(tup,ind) get<ind>(tup)
#define print(x) for (auto i:x){cout<<i<<" ";}cout<<endl;

using namespace std;

int h,w;
char arr[4000][4000];
bool vis[4000][4000];

void fill(int x,int y){
    queue <pair<int,int>> bfs;bfs.emplace(x,y);
    while (bfs.size()){
        auto [a,b]=bfs.front();bfs.pop();
        if (vis[a][b])continue;
        vis[a][b]=true;
        if (a+1<h && arr[a][b]==arr[a+1][b]){bfs.emplace(a+1,b);}
        if (b+1<w && arr[a][b]==arr[a][b+1]){bfs.emplace(a,b+1);}
        if (a>0 && arr[a][b]==arr[a-1][b]){bfs.emplace(a-1,b);}
        if (b>0 && arr[a][b]==arr[a][b-1]){bfs.emplace(a,b-1);}
    }
}

void solve(){

    cin>>h>>w;
    set <char> st;
    for (int i=0;i<h;i++){
        for (int j=0;j<w;j++){
            cin>>arr[i][j];st.emplace(arr[i][j]);
        }
    }

    char lst=arr[0][0];
    int ans=st.size()-st.count('.');

    queue <pair<int,int>> bfs;bfs.emplace(0,0);
    while (bfs.size()){
        auto [a,b]=bfs.front();bfs.pop();
        if (vis[a][b])continue;
        vis[a][b]=true;
        if (a+1<h && ((arr[a][b]==arr[a+1][b]) || (arr[a][b]==lst && arr[a+1][b]!='.'))){bfs.emplace(a+1,b);}
        if (b+1<w && ((arr[a][b]==arr[a][b+1]) || (arr[a][b]==lst && arr[a][b+1]!='.'))){bfs.emplace(a,b+1);}
        if (a>0 && ((arr[a][b]==arr[a-1][b]) || (arr[a][b]==lst && arr[a-1][b]!='.'))){bfs.emplace(a-1,b);}
        if (b>0 && ((arr[a][b]==arr[a][b-1]) || (arr[a][b]==lst && arr[a][b-1]!='.'))){bfs.emplace(a,b-1);}
    }

    for (int i=0;i<h;i++){
        for (int j=0;j<w;j++){
            if (vis[i][j] || arr[i][j]=='.')continue;
            fill(i,j);ans++;
        }
    }

    cout<<ans<<endl;

    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    int no_test=1;
    //cin>>no_test;
    while (no_test--){solve();}
    return 0;
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 6720 KB Output isn't correct
2 Correct 1 ms 2512 KB Output is correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Incorrect 12 ms 6492 KB Output isn't correct
5 Incorrect 4 ms 5724 KB Output isn't correct
6 Correct 1 ms 2396 KB Output is correct
7 Incorrect 1 ms 2652 KB Output isn't correct
8 Incorrect 1 ms 2652 KB Output isn't correct
9 Incorrect 1 ms 2908 KB Output isn't correct
10 Incorrect 4 ms 5468 KB Output isn't correct
11 Incorrect 4 ms 3292 KB Output isn't correct
12 Incorrect 8 ms 5724 KB Output isn't correct
13 Incorrect 4 ms 5724 KB Output isn't correct
14 Incorrect 4 ms 5724 KB Output isn't correct
15 Incorrect 17 ms 6612 KB Output isn't correct
16 Incorrect 21 ms 6708 KB Output isn't correct
17 Incorrect 16 ms 6488 KB Output isn't correct
18 Incorrect 12 ms 6492 KB Output isn't correct

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31324 KB Output is correct
2 Incorrect 68 ms 12996 KB Output isn't correct
3 Incorrect 511 ms 47660 KB Output isn't correct
4 Incorrect 119 ms 21584 KB Output isn't correct
5 Correct 395 ms 35508 KB Output is correct
6 Incorrect 1014 ms 47440 KB Output isn't correct
7 Correct 11 ms 31700 KB Output is correct
8 Correct 10 ms 31324 KB Output is correct
9 Incorrect 3 ms 2396 KB Output isn't correct
10 Correct 2 ms 2648 KB Output is correct
11 Incorrect 9 ms 31324 KB Output isn't correct
12 Correct 2 ms 2908 KB Output is correct
13 Incorrect 68 ms 12880 KB Output isn't correct
14 Incorrect 40 ms 11044 KB Output isn't correct
15 Correct 40 ms 11344 KB Output is correct
16 Incorrect 32 ms 6736 KB Output isn't correct
17 Incorrect 168 ms 22456 KB Output isn't correct
18 Correct 158 ms 22480 KB Output is correct
19 Incorrect 117 ms 21564 KB Output isn't correct
20 Incorrect 115 ms 18768 KB Output isn't correct
21 Incorrect 308 ms 36280 KB Output isn't correct
22 Correct 399 ms 35340 KB Output is correct
23 Incorrect 328 ms 30256 KB Output isn't correct
24 Correct 327 ms 35668 KB Output is correct
25 Correct 589 ms 47520 KB Output is correct
26 Correct 717 ms 42652 KB Output is correct
27 Incorrect 1065 ms 47508 KB Output isn't correct
28 Incorrect 1064 ms 47452 KB Output isn't correct
29 Incorrect 961 ms 47400 KB Output isn't correct
30 Incorrect 1024 ms 46852 KB Output isn't correct
31 Incorrect 765 ms 37204 KB Output isn't correct
32 Incorrect 920 ms 47284 KB Output isn't correct