oj.uz

Submission #1107882

# Submission time Handle Problem Language Result Execution time Memory
1107882 2024-11-02T09:23:55 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
91.25 / 100
 2000 ms 616220 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 26828 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 15 ms 17500 KB Output is correct
5 Correct 9 ms 12368 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 2 ms 4876 KB Output is correct
10 Correct 10 ms 10320 KB Output is correct
11 Correct 5 ms 6908 KB Output is correct
12 Correct 27 ms 14416 KB Output is correct
13 Correct 14 ms 12456 KB Output is correct
14 Correct 9 ms 12368 KB Output is correct
15 Correct 59 ms 26184 KB Output is correct
16 Correct 84 ms 26952 KB Output is correct
17 Correct 46 ms 25424 KB Output is correct
18 Correct 16 ms 17744 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 122704 KB Output is correct
2 Correct 246 ms 85832 KB Output is correct
3 Correct 1481 ms 443708 KB Output is correct
4 Correct 338 ms 117916 KB Output is correct
5 Execution timed out 2112 ms 616220 KB Time limit exceeded
6 Correct 1760 ms 263556 KB Output is correct
7 Correct 15 ms 126544 KB Output is correct
8 Correct 15 ms 122648 KB Output is correct
9 Correct 8 ms 4176 KB Output is correct
10 Correct 4 ms 3040 KB Output is correct
11 Correct 15 ms 124384 KB Output is correct
12 Correct 7 ms 8696 KB Output is correct
13 Correct 225 ms 86920 KB Output is correct
14 Correct 127 ms 55880 KB Output is correct
15 Correct 122 ms 61772 KB Output is correct
16 Correct 120 ms 36288 KB Output is correct
17 Correct 675 ms 181220 KB Output is correct
18 Correct 625 ms 173828 KB Output is correct
19 Correct 325 ms 117320 KB Output is correct
20 Correct 329 ms 128584 KB Output is correct
21 Correct 865 ms 288588 KB Output is correct
22 Execution timed out 2074 ms 599272 KB Time limit exceeded
23 Correct 1192 ms 307024 KB Output is correct
24 Correct 1008 ms 393620 KB Output is correct
25 Execution timed out 2084 ms 577592 KB Time limit exceeded
26 Correct 461 ms 129004 KB Output is correct
27 Correct 620 ms 153160 KB Output is correct
28 Correct 1940 ms 263608 KB Output is correct
29 Correct 1585 ms 216352 KB Output is correct
30 Correct 1196 ms 194680 KB Output is correct
31 Execution timed out 2076 ms 355280 KB Time limit exceeded
32 Correct 626 ms 175004 KB Output is correct