oj.uz

Submission #1108083

# Submission time Handle Problem Language Result Execution time Memory
1108083 2024-11-02T17:30:55 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
75.9375 / 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 = 4e3 +5, inf = INT_MAX, LL = 30;
 
int comp[sze][sze];
int used[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);
    }
}
int a,b;
set<pair<int,int>> lst;
void dfs2(int i,int j){
    if(i<0 || i==n || j<0 || j==m || comp[i][j]==-1 || used[i][j]){
        return;
    }
    used[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]){
            lst.ins({min(comp[a][b],comp[i][j]),max(comp[a][b],comp[i][j])});
        }
        dfs2(a,b);
    }

}
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;
    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++;
            }
        }
    }
    vector<int> graph[ct+11];
    for(int i=0;i<=ct;i++){
        graph[i].clear();
    }
    dfs2(0,0);
    for(auto v:lst){
        graph[v.first].pb(v.second);
        graph[v.second].pb(v.first);
    }
    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;
}

Compilation message

tracks.cpp: In function 'void rush()':
tracks.cpp:53:9: warning: unused variable 'u' [-Wunused-variable]
   53 |     int u,v;
      |         ^
tracks.cpp:53:11: warning: unused variable 'v' [-Wunused-variable]
   53 |     int u,v;
      |           ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 52808 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 2 ms 6992 KB Output is correct
4 Correct 33 ms 41556 KB Output is correct
5 Correct 11 ms 18760 KB Output is correct
6 Correct 1 ms 4688 KB Output is correct
7 Correct 2 ms 6864 KB Output is correct
8 Correct 3 ms 7504 KB Output is correct
9 Correct 3 ms 9296 KB Output is correct
10 Correct 11 ms 16208 KB Output is correct
11 Correct 11 ms 16464 KB Output is correct
12 Correct 33 ms 26060 KB Output is correct
13 Correct 11 ms 18768 KB Output is correct
14 Correct 11 ms 18768 KB Output is correct
15 Correct 59 ms 34160 KB Output is correct
16 Correct 101 ms 52720 KB Output is correct
17 Correct 45 ms 35212 KB Output is correct
18 Correct 34 ms 41432 KB Output is correct

Subtask #2
45.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 157936 KB Output is correct
2 Correct 224 ms 105860 KB Output is correct
3 Correct 1419 ms 586348 KB Output is correct
4 Correct 348 ms 163912 KB Output is correct
5 Runtime error 2000 ms 1048576 KB Execution killed with signal 9
6 Runtime error 1744 ms 1048576 KB Execution killed with signal 9
7 Correct 30 ms 160080 KB Output is correct
8 Correct 30 ms 157768 KB Output is correct
9 Correct 10 ms 5468 KB Output is correct
10 Correct 3 ms 3664 KB Output is correct
11 Correct 28 ms 158956 KB Output is correct
12 Correct 9 ms 14176 KB Output is correct
13 Correct 231 ms 105252 KB Output is correct
14 Correct 129 ms 69560 KB Output is correct
15 Correct 183 ms 101344 KB Output is correct
16 Correct 116 ms 44468 KB Output is correct
17 Correct 551 ms 212164 KB Output is correct
18 Correct 785 ms 305392 KB Output is correct
19 Correct 310 ms 166472 KB Output is correct
20 Correct 295 ms 173384 KB Output is correct
21 Correct 788 ms 381088 KB Output is correct
22 Runtime error 1975 ms 1048576 KB Execution killed with signal 9
23 Correct 1110 ms 358080 KB Output is correct
24 Correct 1197 ms 674320 KB Output is correct
25 Execution timed out 2128 ms 936264 KB Time limit exceeded
26 Runtime error 1501 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1522 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1762 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1623 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1489 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2112 ms 849276 KB Time limit exceeded
32 Runtime error 1722 ms 1048576 KB Execution killed with signal 9