oj.uz

Submission #1108078

# Submission time Handle Problem Language Result Execution time Memory
1108078 2024-11-02T17:06:50 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++11
71.9792 / 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];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};

struct DSU{
    vector<int> parent;
    vector<int> sz;
    DSU(int n){
        sz.resize(n+1,1);
        parent.resize(n+1);
        iota(all(parent),0);
    }
    int root(int node){
        if(parent[node]==node){
            return node;
        }
        return parent[node]=root(parent[node]);
    }
    void unite(int a,int b){
        int x = root(a);
        int y = root(b);
        if(x!=y){
            if(sz[x]<sz[y]){
                swap(x,y);
            }
            parent[y]=x;
            sz[x]+=sz[y];
        }
    }
};
void rush(){
    int n,m;
    cin>>n>>m;  
    DSU dsu(4005*4005);
    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]!='.'){
                if(comp[i][j]==-1){
                    comp[i][j]=(ct++);
                }
                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 && arr[a][b]==arr[i][j]){
                        if(comp[a][b]!=-1){
                            dsu.unite(comp[a][b],comp[i][j]);
                        }
                        comp[a][b]=dsu.root(comp[i][j]);
                    }
                }
            }
        }
    }
    map<int,vector<pair<int,int>>> cp;
    ct=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(comp[i][j]!=-1){
                cp[dsu.root(comp[i][j])].pb({i,j});
            }
        }
    }
    for(auto &v:cp){
        for(auto pp:v.second){
            // cout<<pp.first<<" "<<pp.second<<endl;
            comp[pp.first][pp.second]=ct;
        }
        ct++;
    }
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         cout<<comp[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    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
21.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 283464 KB Output is correct
2 Correct 44 ms 253512 KB Output is correct
3 Correct 39 ms 253512 KB Output is correct
4 Incorrect 56 ms 271668 KB Output isn't correct
5 Correct 47 ms 264232 KB Output is correct
6 Correct 39 ms 253512 KB Output is correct
7 Correct 38 ms 253768 KB Output is correct
8 Incorrect 39 ms 253768 KB Output isn't correct
9 Correct 39 ms 255824 KB Output is correct
10 Correct 48 ms 262312 KB Output is correct
11 Incorrect 43 ms 258772 KB Output isn't correct
12 Incorrect 64 ms 267336 KB Output isn't correct
13 Correct 47 ms 264300 KB Output is correct
14 Correct 47 ms 264376 KB Output is correct
15 Correct 93 ms 281788 KB Output is correct
16 Correct 108 ms 283464 KB Output is correct
17 Correct 78 ms 279680 KB Output is correct
18 Incorrect 57 ms 271548 KB Output isn't correct

Subtask #2
50.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 327888 KB Output is correct
2 Correct 267 ms 358992 KB Output is correct
3 Correct 1578 ms 831708 KB Output is correct
4 Correct 407 ms 368460 KB Output is correct
5 Runtime error 1818 ms 1048576 KB Execution killed with signal 9
6 Execution timed out 2084 ms 796692 KB Time limit exceeded
7 Correct 85 ms 269640 KB Output is correct
8 Correct 90 ms 270928 KB Output is correct
9 Correct 46 ms 255872 KB Output is correct
10 Correct 63 ms 252436 KB Output is correct
11 Correct 90 ms 268616 KB Output is correct
12 Correct 45 ms 260440 KB Output is correct
13 Correct 336 ms 334676 KB Output is correct
14 Correct 212 ms 300616 KB Output is correct
15 Correct 177 ms 310096 KB Output is correct
16 Correct 163 ms 290092 KB Output is correct
17 Correct 651 ms 465996 KB Output is correct
18 Correct 605 ms 461384 KB Output is correct
19 Correct 398 ms 368968 KB Output is correct
20 Correct 423 ms 390756 KB Output is correct
21 Correct 1068 ms 614624 KB Output is correct
22 Runtime error 1832 ms 1048576 KB Execution killed with signal 9
23 Incorrect 1316 ms 660412 KB Output isn't correct
24 Correct 1094 ms 776776 KB Output is correct
25 Execution timed out 2116 ms 1041120 KB Time limit exceeded
26 Correct 881 ms 642884 KB Output is correct
27 Correct 1280 ms 772592 KB Output is correct
28 Execution timed out 2070 ms 792932 KB Time limit exceeded
29 Execution timed out 2100 ms 765364 KB Time limit exceeded
30 Incorrect 1803 ms 717212 KB Output isn't correct
31 Execution timed out 2095 ms 832700 KB Time limit exceeded
32 Correct 1215 ms 668120 KB Output is correct