oj.uz

Submission #1107881

# Submission time Handle Problem Language Result Execution time Memory
1107881 2024-11-02T09:21:22 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
17.6042 / 100
 2000 ms 761844 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1e5 +5, inf = INT_MAX, LL = 30;


int comp[4005][4005];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
void rush(){
    int n,m;
    cin>>n>>m;
 
    vector<vector<char>> arr(n,vector<char>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            comp[i][j]=-1;
            cin>>arr[i][j];
        }
    }
 
    int ct = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]!='*' && comp[i][j]==-1){
                queue<pair<int,int>> q;
                q.push({i,j});
                comp[i][j]=ct;
                while(!q.empty()){
 
                    pair<int,int> node = q.front();q.pop();
                    // cout<<node.first<<" "<<node.second<<endl;
 
                    for(int x=0;x<4;x++){
                        int a = node.first + dx[x];
                        int b =  node.second + dy[x];
                        if(a>=0 && a<n && b>=0 && b<m && comp[a][b]==-1 && arr[a][b]==arr[i][j]){
                            comp[a][b]=ct;
                            q.push({a,b});
                            // cout<<node.first<<" "<<node.second <<" _>"<<a<<" "<<b<<endl;
                        }
                    }
 
                }
                ct++;
            }
 
        }
    }
 
    set<pair<int,int>> edge;
 
    vector<int> graph[ct];
    for(int i =0;i<n;i++){
        for(int j=0;j<m;j++){
            if(comp[i][j]!=-1){
 
                for(int x= 0; x<4;x++){
                    int a = i + dx[x];
                    int b = j + dy[x];
                    if(a>=0 && a<n && b>=0 && b<m && comp[a][b] !=-1 && comp[a][b]!=comp[i][j]){
                        if(edge.find({comp[i][j],comp[a][b]})==edge.end()){
                            edge.insert({comp[i][j],comp[a][b]});
                            graph[comp[i][j]].pb(comp[a][b]);
                        }
                    }
                }
 
            }
        }
    }
    int ans=0;
    queue<pair<int,int>> q;
    vector<int> used(ct,0);
    q.push({0,1});
    used[0]=1;
    while(!q.empty()){
        auto node = q.front();
        ans=max(ans,node.second);
        q.pop();
        for(auto v:graph[node.first]){
        if(!used[v]){
                used[v]=1;
                q.push({v,node.second+1});
            }
        }
    }
    putr(ans);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1; 
    // cin>>tt;

    while(tt--){
        rush();
    }

    return 0;
}

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 28232 KB Output isn't correct
2 Incorrect 1 ms 2556 KB Output isn't correct
3 Incorrect 1 ms 2812 KB Output isn't correct
4 Correct 15 ms 17744 KB Output is correct
5 Incorrect 21 ms 14556 KB Output isn't correct
6 Incorrect 1 ms 2384 KB Output isn't correct
7 Incorrect 2 ms 2568 KB Output isn't correct
8 Correct 2 ms 2384 KB Output is correct
9 Incorrect 3 ms 4688 KB Output isn't correct
10 Incorrect 17 ms 11856 KB Output isn't correct
11 Correct 4 ms 6736 KB Output is correct
12 Incorrect 34 ms 15076 KB Output isn't correct
13 Incorrect 22 ms 14540 KB Output isn't correct
14 Incorrect 21 ms 14528 KB Output isn't correct
15 Incorrect 92 ms 29768 KB Output isn't correct
16 Incorrect 89 ms 28372 KB Output isn't correct
17 Incorrect 102 ms 34816 KB Output isn't correct
18 Correct 15 ms 17760 KB Output is correct

Subtask #2
10.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 124240 KB Output isn't correct
2 Incorrect 441 ms 121800 KB Output isn't correct
3 Execution timed out 2067 ms 539704 KB Time limit exceeded
4 Incorrect 778 ms 187720 KB Output isn't correct
5 Execution timed out 2113 ms 761844 KB Time limit exceeded
6 Execution timed out 2005 ms 271180 KB Time limit exceeded
7 Incorrect 25 ms 127824 KB Output isn't correct
8 Incorrect 23 ms 124240 KB Output isn't correct
9 Incorrect 13 ms 5200 KB Output isn't correct
10 Incorrect 5 ms 3408 KB Output isn't correct
11 Incorrect 16 ms 124520 KB Output isn't correct
12 Incorrect 16 ms 12016 KB Output isn't correct
13 Incorrect 446 ms 121804 KB Output isn't correct
14 Incorrect 254 ms 75980 KB Output isn't correct
15 Incorrect 390 ms 100280 KB Output isn't correct
16 Incorrect 194 ms 49604 KB Output isn't correct
17 Incorrect 1073 ms 277120 KB Output isn't correct
18 Incorrect 1603 ms 341548 KB Output isn't correct
19 Incorrect 798 ms 188304 KB Output isn't correct
20 Incorrect 678 ms 182960 KB Output isn't correct
21 Incorrect 1892 ms 431548 KB Output isn't correct
22 Execution timed out 2114 ms 722080 KB Time limit exceeded
23 Execution timed out 2088 ms 486320 KB Time limit exceeded
24 Execution timed out 2093 ms 684616 KB Time limit exceeded
25 Execution timed out 2084 ms 475632 KB Time limit exceeded
26 Correct 418 ms 133964 KB Output is correct
27 Correct 630 ms 160888 KB Output is correct
28 Correct 1905 ms 270996 KB Output is correct
29 Correct 1653 ms 223860 KB Output is correct
30 Correct 1242 ms 202288 KB Output is correct
31 Execution timed out 2047 ms 365720 KB Time limit exceeded
32 Incorrect 870 ms 206276 KB Output isn't correct