Submission #488835

#	Time	Username	Problem	Language	Result	Execution time	Memory
488835		beedle	Tracks in the Snow (BOI13_tracks)	C++17	67.19 / 100	2112 ms	1048576 KiB

tracks

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#define pi 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 1000000007
#define INF 1000000000000000000
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

string g[4000];
int group[4000][4000];
bool marked[4000][4000];
vector <pair<int,int>> dir={{0,1},{0,-1},{1,0},{-1,0}};
int n,m;

int curr=1;

void dfs(int i, int j)
{
    marked[i][j]=true;
    group[i][j]=curr;
    for(auto mv:dir)
    {
        ll v1=i+mv.ff;
        ll v2=j+mv.ss;
        if(v1>=0 && v2>=0 && v1<n && v2<m && !marked[v1][v2])
        if(g[i][j]==g[v1][v2])
        {
            dfs(v1,v2);
        }
    }
}

signed main()
{
    fast;
 
    cin>>n>>m;

    rep(i,0,n-1)
    cin>>g[i];

    rep(i,0,n-1)
    rep(j,0,m-1)
    marked[i][j]=false, group[i][j]=0;

    rep(i,0,n-1)
    rep(j,0,m-1)
    if(!marked[i][j])
    if(g[i][j]=='F' || g[i][j]=='R')
    {
        dfs(i,j);
        curr+=1;
    }

    map <pair<int,int>,bool> done; 
    vector <int> adj[curr];

    rep(i,0,n-1)
    rep(j,0,m-1)
    {
        for(auto mv:dir)
        {
            ll v1=i+mv.ff;
            ll v2=j+mv.ss;
            if(v1>=0 && v2>=0 && v1<n && v2<m)
            {
                ll g1=group[i][j];
                ll g2=group[v1][v2];

                if(!done[{g1,g2}] && g1>0 && g2>0)
                {
                    adj[g1].pb(g2);
                    adj[g2].pb(g1);
                    done[{g1,g2}]=true;
                    done[{g2,g1}]=true;
                }
            }
        }
    }

    queue <int> q;
    vector <bool> used(curr);
    vector<int> d(curr), p(curr);

    q.push(group[0][0]);
    used[group[0][0]] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (!used[u]) {
                used[u] = true;
                q.push(u);
                d[u] = d[v] + 1;
            }
        }
    }

    int ans=0;
    rep(i,0,curr-1)
    ans=max(ans,d[i]);

    cout<<1+ans;
    // rep(i,0,n-1)
    // rep(j,0,m-1)
    // cout<<group[i][j]<<" ";

    return 0;
}

/*
5 8 
FFR..... 
.FRRR... 
.FFFFF.. 
..RRRFFR 
.....FFF
*/

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