Submission #715652

#	Time	Username	Problem	Language	Result	Execution time	Memory
715652		Makarooni	Tracks in the Snow (BOI13_tracks)	C++17	67.19 / 100	2135 ms	990004 KiB

tracks

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

#define all(x) x.begin(), x.end()
#define pb(x) push_back(x)
#define endl '\n'
#define sz(x) (int)x.size()
#define mr(x, y) make_pair(x, y)
#define F first
#define S second
#define pii pair<int, int>

const int N = 4e3 + 10;
const int MOD = 1e9 + 7;

char c[N][N];
pair<int, int> par[N][N];
set<pii> pars;
vector<pair<int, int>> vec[N][N];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}, n, m;
pii nxt;

string s[10];

void merge(pair<int, int> u, pair<int, int> v){
    if(par[u.F][u.S] == par[v.F][v.S])
        return;
    u = par[u.F][u.S], v = par[v.F][v.S];
    if(sz(vec[u.F][u.S]) > sz(vec[v.F][v.S]))
        swap(u, v);
    pars.erase(u);
    for(pair<int, int> y : vec[u.F][u.S]){
        par[y.F][y.S] = v;
        vec[v.F][v.S].pb(y);
    }
    vec[u.F][u.S].clear();
}

void upd(pair<int, int> v){
    c[v.F][v.S] = 'O';
    pars.erase(v);
    vector<pair<int, int>> r, f;
    for(pair<int, int> y : vec[v.F][v.S]){
        int i = y.F, j = y.S;
        for(int k = 0; k < 4; k++){
            if(i + dx[k] > 0 && i + dx[k] <= n && j + dy[k] > 0 && j + dy[k] <= m){
                pii t = par[i + dx[k]][j + dy[k]];
                if(c[t.F][t.S] == 'O' || c[t.F][t.S] == '.')
                    continue;
                //cout << i + dx[k] << " " << j + dy[k] << endl;
                if(c[i + dx[k]][j + dy[k]] == 'R')
                    r.pb(mr(i + dx[k], j + dy[k]));
                else if(c[i + dx[k]][j + dy[k]] == 'F')
                    f.pb(mr(i + dx[k], j + dy[k]));
            }
        }
    }
    //exit(0);
    for(int i = 1; i < sz(r); i++)
        merge(r[i], r[i - 1]);
    for(int i = 1; i < sz(f); i++)
        merge(f[i], f[i - 1]);
	if(sz(r) == 0 && sz(f) == 0)
		nxt = mr(-1, -1);
	else if(sz(r) == 0)
		nxt = par[f[0].F][f[0].S];
	else
		nxt = par[r[0].F][r[0].S];
}

int main(){
    ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
   cin >> n >> m;
   /* n = 5, m = 8;
    s[1] = "!FFR.....";
    s[2] = "!.FRRR...";
    s[3] = "!.FFFFF..";
    s[4] = "!..RRRFFR";
    s[5] = "!.....FFF";*/
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> c[i][j];
			//c[i][j] = s[i][j];
            if(c[i][j] == '.')
                continue;
            pars.insert(mr(i, j));
            par[i][j] = mr(i, j);
            vec[i][j].pb(mr(i, j));
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int k = 0; k < 4; k++){
                if(i + dx[k] > 0 && i + dx[k] <= n && j + dy[k] > 0 && j + dy[k] <= m){
                    if(c[i][j] != '.' && c[i][j] == c[i + dx[k]][j + dy[k]])
                        merge(mr(i, j), mr(i + dx[k], j + dy[k]));
                }
            }
        }
    }
    int ans = 1;
    upd(par[1][1]);
    while(!pars.empty()){
        upd(nxt);
        ans++;
    }
    cout << ans;
}

Compilation message (stderr)

tracks.cpp: In function 'void upd(std::pair<int, int>)':
tracks.cpp:61:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   61 |     for(int i = 1; i < sz(f); i++)
      |     ^~~
tracks.cpp:63:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   63 |  if(sz(r) == 0 && sz(f) == 0)
      |  ^~

• Subtask 1: 30 / 30
• Subtask 2: 37.1875 / 70