oj.uz

Submission #488838

# Submission time Handle Problem Language Result Execution time Memory
488838 2021-11-20T15:31:45 Z beedle Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 2000 ms 1045856 KB 
#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;
    }

    set <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(g1>0 && g2>0)
                if(!adj[g1].count(g2))
                {
                    adj[g1].insert(g2);
                    adj[g2].insert(g1);
                }
            }
        }
    }

    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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 22 ms 6460 KB Output is correct
5 Correct 7 ms 4684 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1356 KB Output is correct
10 Correct 9 ms 4328 KB Output is correct
11 Correct 5 ms 2764 KB Output is correct
12 Correct 24 ms 6088 KB Output is correct
13 Correct 7 ms 4684 KB Output is correct
14 Correct 7 ms 4684 KB Output is correct
15 Correct 38 ms 13260 KB Output is correct
16 Correct 48 ms 13604 KB Output is correct
17 Correct 27 ms 12492 KB Output is correct
18 Correct 17 ms 6484 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31692 KB Output is correct
2 Correct 159 ms 57352 KB Output is correct
3 Correct 819 ms 366976 KB Output is correct
4 Correct 223 ms 83608 KB Output is correct
5 Correct 1093 ms 742212 KB Output is correct
6 Correct 1965 ms 203168 KB Output is correct
7 Correct 16 ms 33100 KB Output is correct
8 Correct 16 ms 31756 KB Output is correct
9 Correct 6 ms 2024 KB Output is correct
10 Correct 2 ms 1228 KB Output is correct
11 Correct 17 ms 32148 KB Output is correct
12 Correct 4 ms 3276 KB Output is correct
13 Correct 153 ms 57356 KB Output is correct
14 Correct 90 ms 34896 KB Output is correct
15 Correct 82 ms 38732 KB Output is correct
16 Correct 84 ms 25060 KB Output is correct
17 Correct 389 ms 138284 KB Output is correct
18 Correct 378 ms 134828 KB Output is correct
19 Correct 220 ms 83604 KB Output is correct
20 Correct 247 ms 95080 KB Output is correct
21 Correct 493 ms 233928 KB Output is correct
22 Correct 1022 ms 742060 KB Output is correct
23 Correct 762 ms 251848 KB Output is correct
24 Correct 570 ms 332708 KB Output is correct
25 Correct 1595 ms 493296 KB Output is correct
26 Correct 979 ms 1045856 KB Output is correct
27 Correct 1295 ms 320712 KB Output is correct
28 Correct 1924 ms 200088 KB Output is correct
29 Correct 1866 ms 168556 KB Output is correct
30 Correct 1761 ms 237308 KB Output is correct
31 Execution timed out 2111 ms 400720 KB Time limit exceeded
32 Correct 1485 ms 453744 KB Output is correct