oj.uz

Submission #1107985

# Submission time Handle Problem Language Result Execution time Memory
1107985 2024-11-02T14:13:00 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++11
97.8125 / 100
 2000 ms 771912 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;
    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){
                queue<pair<int,int>> q;
                q.push({i,j});
                comp[i][j]=ct;
                while(!q.empty()){
 
                    pair<int,int> node = q.front();q.pop();
                    for(int x=0;x<4;x++){
                        a = node.first + dx[x];
                        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});
                        }
                    }
 
                }
                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 45 ms 24136 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 12 ms 17324 KB Output is correct
5 Correct 6 ms 12112 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 4688 KB Output is correct
10 Correct 6 ms 10064 KB Output is correct
11 Correct 4 ms 6736 KB Output is correct
12 Correct 18 ms 13388 KB Output is correct
13 Correct 7 ms 12112 KB Output is correct
14 Correct 6 ms 12116 KB Output is correct
15 Correct 35 ms 23624 KB Output is correct
16 Correct 45 ms 24136 KB Output is correct
17 Correct 26 ms 23120 KB Output is correct
18 Correct 13 ms 17488 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 122448 KB Output is correct
2 Correct 133 ms 75848 KB Output is correct
3 Correct 774 ms 369492 KB Output is correct
4 Correct 210 ms 103752 KB Output is correct
5 Correct 1277 ms 771900 KB Output is correct
6 Correct 1666 ms 228072 KB Output is correct
7 Correct 15 ms 126544 KB Output is correct
8 Correct 15 ms 122448 KB Output is correct
9 Correct 6 ms 3664 KB Output is correct
10 Correct 2 ms 2896 KB Output is correct
11 Correct 14 ms 123984 KB Output is correct
12 Correct 4 ms 8272 KB Output is correct
13 Correct 143 ms 75848 KB Output is correct
14 Correct 75 ms 49224 KB Output is correct
15 Correct 91 ms 55368 KB Output is correct
16 Correct 66 ms 30792 KB Output is correct
17 Correct 365 ms 152988 KB Output is correct
18 Correct 358 ms 150088 KB Output is correct
19 Correct 187 ms 103752 KB Output is correct
20 Correct 177 ms 111176 KB Output is correct
21 Correct 432 ms 244552 KB Output is correct
22 Correct 1158 ms 771912 KB Output is correct
23 Correct 648 ms 252304 KB Output is correct
24 Correct 518 ms 330668 KB Output is correct
25 Correct 1693 ms 480280 KB Output is correct
26 Correct 409 ms 123620 KB Output is correct
27 Correct 624 ms 144256 KB Output is correct
28 Correct 1599 ms 228004 KB Output is correct
29 Correct 1508 ms 192624 KB Output is correct
30 Correct 1102 ms 176088 KB Output is correct
31 Execution timed out 2077 ms 402248 KB Time limit exceeded
32 Correct 619 ms 162376 KB Output is correct