oj.uz

Submission #1107885

# Submission time Handle Problem Language Result Execution time Memory
1107885 2024-11-02T09:29:01 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
91.25 / 100
 2000 ms 1048576 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];
unordered_map<int,unordered_map<int,int>> edg;
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();
                    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});
                        }
                    }
 
                }
                ct++;
            }
 
        }
    }
 
    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(edg[comp[i][j]][comp[a][b]]==0 ){
                            edg[comp[i][j]][comp[a][b]]=1;
                            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 55 ms 30120 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 12 ms 18000 KB Output is correct
5 Correct 9 ms 13392 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2640 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 2 ms 4688 KB Output is correct
10 Correct 10 ms 11344 KB Output is correct
11 Correct 4 ms 6992 KB Output is correct
12 Correct 18 ms 15440 KB Output is correct
13 Correct 12 ms 13392 KB Output is correct
14 Correct 9 ms 13392 KB Output is correct
15 Correct 39 ms 29860 KB Output is correct
16 Correct 48 ms 30120 KB Output is correct
17 Correct 34 ms 29092 KB Output is correct
18 Correct 13 ms 18000 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 123472 KB Output is correct
2 Correct 268 ms 110520 KB Output is correct
3 Correct 1350 ms 617732 KB Output is correct
4 Correct 289 ms 147568 KB Output is correct
5 Runtime error 1884 ms 1048576 KB Execution killed with signal 9
6 Correct 1465 ms 347916 KB Output is correct
7 Correct 17 ms 127312 KB Output is correct
8 Correct 17 ms 123472 KB Output is correct
9 Correct 10 ms 4944 KB Output is correct
10 Correct 3 ms 3416 KB Output is correct
11 Correct 15 ms 124572 KB Output is correct
12 Correct 7 ms 10076 KB Output is correct
13 Correct 209 ms 112036 KB Output is correct
14 Correct 118 ms 70076 KB Output is correct
15 Correct 148 ms 81176 KB Output is correct
16 Correct 112 ms 47548 KB Output is correct
17 Correct 630 ms 246568 KB Output is correct
18 Correct 623 ms 250036 KB Output is correct
19 Correct 305 ms 151156 KB Output is correct
20 Correct 305 ms 171156 KB Output is correct
21 Correct 807 ms 406376 KB Output is correct
22 Runtime error 1491 ms 1048576 KB Execution killed with signal 9
23 Correct 1020 ms 432556 KB Output is correct
24 Correct 976 ms 608392 KB Output is correct
25 Execution timed out 2124 ms 893304 KB Time limit exceeded
26 Correct 439 ms 134112 KB Output is correct
27 Correct 593 ms 163144 KB Output is correct
28 Correct 1505 ms 347904 KB Output is correct
29 Correct 1319 ms 270448 KB Output is correct
30 Correct 1071 ms 235964 KB Output is correct
31 Execution timed out 2118 ms 651396 KB Time limit exceeded
32 Correct 619 ms 199428 KB Output is correct