oj.uz

Submission #631279

# Submission time Handle Problem Language Result Execution time Memory
631279 2022-08-18T02:24:55 Z czhang2718 Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 2000 ms 722400 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 vis[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;
    int r=find(0);
    q.push(r);
    for(; !q.empty(); q.pop()){
        int x=q.front();
        for(int k:adj[x]){
            if(!vis[k] && k!=r){
                vis[k]=vis[x]+1;
                // cout << "vis[" << k << "] = " << vis[k] << "\n";
                q.push(k);
            }
        }
    }
    int mx=0;
    for(int i=0; i<n*m; i++) mx=max(mx, vis[i]);
    cout << mx+1;
}
// when its been a long time since goodbye

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 384192 KB Output is correct
2 Correct 173 ms 376168 KB Output is correct
3 Correct 170 ms 376136 KB Output is correct
4 Correct 189 ms 378700 KB Output is correct
5 Correct 174 ms 377340 KB Output is correct
6 Correct 171 ms 376268 KB Output is correct
7 Correct 175 ms 376168 KB Output is correct
8 Correct 177 ms 376196 KB Output is correct
9 Correct 171 ms 376232 KB Output is correct
10 Correct 183 ms 377368 KB Output is correct
11 Correct 175 ms 376732 KB Output is correct
12 Correct 190 ms 378980 KB Output is correct
13 Correct 189 ms 377384 KB Output is correct
14 Correct 178 ms 377404 KB Output is correct
15 Correct 210 ms 382860 KB Output is correct
16 Correct 215 ms 384120 KB Output is correct
17 Correct 212 ms 380824 KB Output is correct
18 Correct 181 ms 378824 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 376808 KB Output is correct
2 Correct 312 ms 406080 KB Output is correct
3 Correct 861 ms 580756 KB Output is correct
4 Correct 343 ms 426608 KB Output is correct
5 Correct 935 ms 585292 KB Output is correct
6 Correct 1769 ms 646804 KB Output is correct
7 Correct 176 ms 376724 KB Output is correct
8 Correct 180 ms 376912 KB Output is correct
9 Correct 182 ms 377200 KB Output is correct
10 Correct 190 ms 376472 KB Output is correct
11 Correct 189 ms 376800 KB Output is correct
12 Correct 174 ms 376672 KB Output is correct
13 Correct 300 ms 406092 KB Output is correct
14 Correct 272 ms 393528 KB Output is correct
15 Correct 238 ms 391340 KB Output is correct
16 Correct 234 ms 390376 KB Output is correct
17 Correct 519 ms 450696 KB Output is correct
18 Correct 481 ms 436788 KB Output is correct
19 Correct 351 ms 426420 KB Output is correct
20 Correct 350 ms 426600 KB Output is correct
21 Correct 562 ms 501436 KB Output is correct
22 Correct 918 ms 585412 KB Output is correct
23 Correct 850 ms 516172 KB Output is correct
24 Correct 609 ms 497228 KB Output is correct
25 Correct 1515 ms 621688 KB Output is correct
26 Correct 676 ms 437556 KB Output is correct
27 Correct 907 ms 520496 KB Output is correct
28 Correct 1540 ms 647012 KB Output is correct
29 Correct 1374 ms 633220 KB Output is correct
30 Correct 1206 ms 595984 KB Output is correct
31 Execution timed out 2124 ms 722400 KB Time limit exceeded
32 Correct 864 ms 525052 KB Output is correct