Submission #940064

#	Time	Username	Problem	Language	Result	Execution time	Memory
940064		VKnight	Tracks in the Snow (BOI13_tracks)	C++17	29.58 / 100	1065 ms	47660 KiB

tracks

#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.3333333333333335 / 30
• Subtask 2: 26.25 / 70