Submission #1306428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306428		somefolk	Tracks in the Snow (BOI13_tracks)	C++20	27.40 / 100	2128 ms	824864 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

const int N = 4005;

int n, m;
char a[N][N];
int c1 = 0, c2 = 0;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int vis[N][N];

bool check(int i, int j, char c){
    return (i >= 0 && i < n && j >= 0 && j < m && a[i][j] == c && !vis[i][j]);
}

void cover(int i0, int j0){
    queue<pair<int, int>> q;
    q.push({i0, j0});
    vis[i0][j0] = true;

    while(!q.empty()){
        int i = q.front().first, j = q.front().second; q.pop();
        vis[i][j] = true;
        if(a[i][j] == 'F') c1--;
        if(a[i][j] == 'R') c2--;
        for(int op = 0; op < 4; op++){
            int i1 = i + dy[op];
            int j1 = j + dx[op];
            if(check(i1, j1, a[i][j])){
                q.push({i1, j1});
            }
        }
        a[i][j] = '.';
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j];

    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
        if(a[i][j] == 'F') c1++;
        if(a[i][j] == 'R') c2++;
    }

    int sol = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(c1 == 0 && c2 == 0){ cout << sol << endl; return; }
            if(c1 == 0 || c2 == 0){ cout << ++sol << endl; return; }
            if(a[i][j] != '.'){
                cover(i, j);
                sol++;
            }
        }
    }

    cout << sol << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

• Subtask 1: 3.3333 / 30
• Subtask 2: 24.0625 / 70