oj.uz

Submission #631277

# Submission time Handle Problem Language Result Execution time Memory
631277 2022-08-18T02:22:43 Z czhang2718 Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 2000 ms 722336 KB 
#include "bits/stdc++.h"
using namespace std;

const int N=4000;
int n, m;
string grid[N];
int par[N*N];
short rnk[N*N];
short dx[]={0, 0, 1, -1};
short dy[]={1, -1, 0, 0};
vector<int> adj[N*N];

int find(int x){ return par[x]==x?x:par[x]=find(par[x]); }

void join(int x, int y){
    int a=find(x);
    int b=find(y);
    if(a==b) return;
    if(rnk[a]<rnk[b]) par[a]=b;
    else if(rnk[b]<rnk[a]) par[b]=a;
    else{
        rnk[a]++;
        par[b]=a;
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++) par[i*m+j]=i*m+j;
        cin >> grid[i];
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(grid[i][j]=='.') continue;
            for(int k=0; k<4; k++){
                int x=i+dx[k];
                int y=j+dy[k];
                if(x<0 || x==n || y<0 || y==m || grid[x][y]!=grid[i][j]) continue;
                join(m*i+j, m*x+y);
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(grid[i][j]=='.') continue;
            for(int k=0; k<4; k++){
                int x=i+dx[k];
                int y=j+dy[k];
                if(x<0 || x==n || y<0 || y==m || grid[x][y]==grid[i][j] || grid[x][y]=='.') continue;
                int a=find(m*i+j), b=find(m*x+y);
                adj[a].push_back(b);
                adj[b].push_back(a);
            }
        }
    }

    // for(int i=0; i<n*m; i++){
    //     if(find(i)!=i) continue;
    //     sort(adj[i].begin(), adj[i].end());
    //     adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    //     // for(int k:adj[i]) cout << i << " " << k << "\n";
    // }

    queue<int> q;
    q.push(find(0));
    vector<int> vis(n*m);
    for(; !q.empty(); q.pop()){
        int x=q.front();
        for(int k:adj[x]){
            if(!vis[k] && k!=find(0)){
                vis[k]=vis[x]+1;
                // cout << "vis[" << k << "] = " << vis[k] << "\n";
                q.push(k);
            }
        }
    }
    cout << *max_element(vis.begin(), vis.end())+1;
}
// when its been a long time since goodbye

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 384088 KB Output is correct
2 Correct 163 ms 376192 KB Output is correct
3 Correct 172 ms 376268 KB Output is correct
4 Correct 179 ms 378724 KB Output is correct
5 Correct 186 ms 377460 KB Output is correct
6 Correct 165 ms 376080 KB Output is correct
7 Correct 169 ms 376180 KB Output is correct
8 Correct 164 ms 376268 KB Output is correct
9 Correct 171 ms 376228 KB Output is correct
10 Correct 172 ms 377380 KB Output is correct
11 Correct 172 ms 376824 KB Output is correct
12 Correct 179 ms 378944 KB Output is correct
13 Correct 173 ms 377356 KB Output is correct
14 Correct 189 ms 377360 KB Output is correct
15 Correct 198 ms 382820 KB Output is correct
16 Correct 205 ms 384152 KB Output is correct
17 Correct 204 ms 380748 KB Output is correct
18 Correct 176 ms 378732 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 376816 KB Output is correct
2 Correct 296 ms 406228 KB Output is correct
3 Correct 801 ms 612700 KB Output is correct
4 Correct 330 ms 426580 KB Output is correct
5 Correct 853 ms 597036 KB Output is correct
6 Correct 1373 ms 646924 KB Output is correct
7 Correct 175 ms 376652 KB Output is correct
8 Correct 174 ms 376772 KB Output is correct
9 Correct 177 ms 377256 KB Output is correct
10 Correct 173 ms 376632 KB Output is correct
11 Correct 171 ms 376624 KB Output is correct
12 Correct 169 ms 376716 KB Output is correct
13 Correct 290 ms 406240 KB Output is correct
14 Correct 241 ms 393500 KB Output is correct
15 Correct 234 ms 391436 KB Output is correct
16 Correct 233 ms 390432 KB Output is correct
17 Correct 478 ms 453192 KB Output is correct
18 Correct 433 ms 436812 KB Output is correct
19 Correct 336 ms 426480 KB Output is correct
20 Correct 328 ms 430112 KB Output is correct
21 Correct 563 ms 516896 KB Output is correct
22 Correct 817 ms 597012 KB Output is correct
23 Correct 774 ms 524564 KB Output is correct
24 Correct 542 ms 514908 KB Output is correct
25 Correct 1391 ms 621612 KB Output is correct
26 Correct 683 ms 485432 KB Output is correct
27 Correct 860 ms 549216 KB Output is correct
28 Correct 1362 ms 646872 KB Output is correct
29 Correct 1271 ms 633260 KB Output is correct
30 Correct 1132 ms 604436 KB Output is correct
31 Execution timed out 2076 ms 722336 KB Time limit exceeded
32 Correct 812 ms 551668 KB Output is correct