oj.uz

Submission #1108080

# Submission time Handle Problem Language Result Execution time Memory
1108080 2024-11-02T17:20:11 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
97.8125 / 100
 2000 ms 895740 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 = 4e3 +5, inf = INT_MAX, LL = 30;
 
int comp[sze][sze];
char arr[sze][sze];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
int ct=0;
int n,m;
void dfs(int i,int j,char ch){
    if(i<0 || i==n || j<0 || j==m || comp[i][j]!=-1 || arr[i][j]!=ch){
        return;
    }
    comp[i][j]=ct;
    for(int x =0;x<4;x++){
        dfs(i+dx[x],j+dy[x],ch);
    }
}

void rush(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            comp[i][j]=-1;
            cin>>arr[i][j];
        }
    }
 
    int u,v,a,b;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]!='.' && comp[i][j]==-1){
                dfs(i,j,arr[i][j]);
                ct++;
            }
        }
    }
    set<int> graph[ct+11];
    for(int i=0;i<=ct;i++){
        graph[i].clear();
    }
    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++){
                    a = i + dx[x];
                    b = j + dy[x];
                    if(a>=0 && a<n && b>=0 && b<m && comp[a][b] !=-1 && comp[a][b]!=comp[i][j]){
                        u = min(comp[i][j],comp[a][b]);
                        v =max(comp[i][j],comp[a][b]);
                        graph[u].ins(v);
                        graph[v].ins(u);
                    }
                }
 
            }
        }
    }
    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);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        rush();
    }
 
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 28372 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 13 ms 22192 KB Output is correct
5 Correct 6 ms 14160 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 6736 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 8784 KB Output is correct
10 Correct 6 ms 14160 KB Output is correct
11 Correct 4 ms 11404 KB Output is correct
12 Correct 16 ms 15440 KB Output is correct
13 Correct 6 ms 14300 KB Output is correct
14 Correct 6 ms 14160 KB Output is correct
15 Correct 32 ms 27732 KB Output is correct
16 Correct 43 ms 28232 KB Output is correct
17 Correct 23 ms 25168 KB Output is correct
18 Correct 13 ms 22352 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 136796 KB Output is correct
2 Correct 116 ms 81480 KB Output is correct
3 Correct 665 ms 375500 KB Output is correct
4 Correct 161 ms 110800 KB Output is correct
5 Correct 1077 ms 785224 KB Output is correct
6 Correct 1575 ms 259180 KB Output is correct
7 Correct 15 ms 140888 KB Output is correct
8 Correct 15 ms 136784 KB Output is correct
9 Correct 5 ms 3664 KB Output is correct
10 Correct 2 ms 2896 KB Output is correct
11 Correct 16 ms 140544 KB Output is correct
12 Correct 4 ms 10320 KB Output is correct
13 Correct 128 ms 80804 KB Output is correct
14 Correct 71 ms 54560 KB Output is correct
15 Correct 82 ms 59468 KB Output is correct
16 Correct 61 ms 33104 KB Output is correct
17 Correct 317 ms 160104 KB Output is correct
18 Correct 311 ms 157980 KB Output is correct
19 Correct 185 ms 113536 KB Output is correct
20 Correct 164 ms 120136 KB Output is correct
21 Correct 424 ms 255560 KB Output is correct
22 Correct 1099 ms 784084 KB Output is correct
23 Correct 607 ms 258460 KB Output is correct
24 Correct 448 ms 340340 KB Output is correct
25 Correct 1347 ms 480384 KB Output is correct
26 Correct 1170 ms 895740 KB Output is correct
27 Correct 970 ms 439868 KB Output is correct
28 Correct 1568 ms 245136 KB Output is correct
29 Correct 1396 ms 217232 KB Output is correct
30 Correct 1264 ms 283504 KB Output is correct
31 Execution timed out 2053 ms 408524 KB Time limit exceeded
32 Correct 1024 ms 430664 KB Output is correct