oj.uz

Submission #488845

# Submission time Handle Problem Language Result Execution time Memory
488845 2021-11-20T15:41:07 Z beedle Tracks in the Snow (BOI13_tracks) C++17
84.6875 / 100
 2000 ms 1041232 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)
                {
                    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 62 ms 13508 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 28 ms 6456 KB Output is correct
5 Correct 8 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 7 ms 4300 KB Output is correct
11 Correct 7 ms 2764 KB Output is correct
12 Correct 22 ms 6092 KB Output is correct
13 Correct 7 ms 4640 KB Output is correct
14 Correct 8 ms 4684 KB Output is correct
15 Correct 51 ms 13392 KB Output is correct
16 Correct 64 ms 13524 KB Output is correct
17 Correct 32 ms 12512 KB Output is correct
18 Correct 28 ms 6468 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31692 KB Output is correct
2 Correct 180 ms 57164 KB Output is correct
3 Correct 957 ms 361824 KB Output is correct
4 Correct 247 ms 80872 KB Output is correct
5 Correct 1102 ms 740736 KB Output is correct
6 Execution timed out 2095 ms 166504 KB Time limit exceeded
7 Correct 15 ms 32972 KB Output is correct
8 Correct 15 ms 31704 KB Output is correct
9 Correct 6 ms 1972 KB Output is correct
10 Correct 2 ms 1228 KB Output is correct
11 Correct 14 ms 32136 KB Output is correct
12 Correct 3 ms 3276 KB Output is correct
13 Correct 177 ms 55840 KB Output is correct
14 Correct 109 ms 34072 KB Output is correct
15 Correct 88 ms 37768 KB Output is correct
16 Correct 89 ms 24408 KB Output is correct
17 Correct 472 ms 134412 KB Output is correct
18 Correct 337 ms 130896 KB Output is correct
19 Correct 232 ms 80124 KB Output is correct
20 Correct 220 ms 91660 KB Output is correct
21 Correct 585 ms 229352 KB Output is correct
22 Correct 1127 ms 741016 KB Output is correct
23 Correct 893 ms 247260 KB Output is correct
24 Correct 636 ms 328440 KB Output is correct
25 Correct 1630 ms 488916 KB Output is correct
26 Correct 1261 ms 1041232 KB Output is correct
27 Execution timed out 2123 ms 318300 KB Time limit exceeded
28 Execution timed out 2100 ms 165268 KB Time limit exceeded
29 Execution timed out 2101 ms 144948 KB Time limit exceeded
30 Execution timed out 2108 ms 222056 KB Time limit exceeded
31 Execution timed out 2117 ms 346016 KB Time limit exceeded
32 Execution timed out 2141 ms 450044 KB Time limit exceeded