oj.uz

Submission #488835

# Submission time Handle Problem Language Result Execution time Memory
488835 2021-11-20T15:29:07 Z beedle Tracks in the Snow (BOI13_tracks) C++17
67.1875 / 100
 2000 ms 1048576 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;
    }

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

# Verdict Execution time Memory Grader output
1 Correct 114 ms 16732 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 976 KB Output is correct
4 Correct 27 ms 6736 KB Output is correct
5 Correct 33 ms 6040 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 2 ms 976 KB Output is correct
8 Correct 2 ms 976 KB Output is correct
9 Correct 3 ms 1488 KB Output is correct
10 Correct 22 ms 5576 KB Output is correct
11 Correct 7 ms 2900 KB Output is correct
12 Correct 42 ms 7396 KB Output is correct
13 Correct 23 ms 6064 KB Output is correct
14 Correct 24 ms 5940 KB Output is correct
15 Correct 111 ms 18416 KB Output is correct
16 Correct 124 ms 16772 KB Output is correct
17 Correct 110 ms 18708 KB Output is correct
18 Correct 26 ms 6720 KB Output is correct

Subtask #2
37.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 32716 KB Output is correct
2 Correct 658 ms 90784 KB Output is correct
3 Execution timed out 2069 ms 351612 KB Time limit exceeded
4 Correct 1102 ms 128028 KB Output is correct
5 Execution timed out 2102 ms 623396 KB Time limit exceeded
6 Execution timed out 2081 ms 204512 KB Time limit exceeded
7 Correct 24 ms 33940 KB Output is correct
8 Correct 31 ms 32648 KB Output is correct
9 Correct 19 ms 3236 KB Output is correct
10 Correct 5 ms 1744 KB Output is correct
11 Correct 21 ms 32644 KB Output is correct
12 Correct 16 ms 5172 KB Output is correct
13 Correct 627 ms 90716 KB Output is correct
14 Correct 370 ms 54592 KB Output is correct
15 Correct 440 ms 63288 KB Output is correct
16 Correct 291 ms 39596 KB Output is correct
17 Correct 1679 ms 226372 KB Output is correct
18 Execution timed out 2050 ms 229720 KB Time limit exceeded
19 Correct 1097 ms 128248 KB Output is correct
20 Correct 1159 ms 152384 KB Output is correct
21 Execution timed out 2095 ms 326724 KB Time limit exceeded
22 Execution timed out 2091 ms 636352 KB Time limit exceeded
23 Execution timed out 2099 ms 330984 KB Time limit exceeded
24 Execution timed out 2101 ms 419192 KB Time limit exceeded
25 Execution timed out 2082 ms 374596 KB Time limit exceeded
26 Correct 1153 ms 1048576 KB Output is correct
27 Execution timed out 2049 ms 335800 KB Time limit exceeded
28 Execution timed out 2075 ms 201432 KB Time limit exceeded
29 Execution timed out 2062 ms 177184 KB Time limit exceeded
30 Execution timed out 2092 ms 251660 KB Time limit exceeded
31 Execution timed out 2105 ms 261676 KB Time limit exceeded
32 Execution timed out 2112 ms 486468 KB Time limit exceeded