oj.uz

Submission #631274

# Submission time Handle Problem Language Result Execution time Memory
631274 2022-08-18T02:20:44 Z czhang2718 Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 2000 ms 682036 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 228 ms 384076 KB Output is correct
2 Correct 178 ms 376196 KB Output is correct
3 Correct 194 ms 376232 KB Output is correct
4 Correct 208 ms 378744 KB Output is correct
5 Correct 196 ms 377416 KB Output is correct
6 Correct 198 ms 376188 KB Output is correct
7 Correct 191 ms 376216 KB Output is correct
8 Correct 216 ms 376228 KB Output is correct
9 Correct 188 ms 376308 KB Output is correct
10 Correct 184 ms 377356 KB Output is correct
11 Correct 193 ms 376832 KB Output is correct
12 Correct 206 ms 378944 KB Output is correct
13 Correct 200 ms 377376 KB Output is correct
14 Correct 229 ms 377412 KB Output is correct
15 Correct 228 ms 382844 KB Output is correct
16 Correct 249 ms 384152 KB Output is correct
17 Correct 212 ms 380840 KB Output is correct
18 Correct 197 ms 378688 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 376824 KB Output is correct
2 Correct 358 ms 406252 KB Output is correct
3 Correct 1020 ms 612496 KB Output is correct
4 Correct 421 ms 426572 KB Output is correct
5 Correct 1037 ms 597024 KB Output is correct
6 Correct 1866 ms 646868 KB Output is correct
7 Correct 201 ms 376708 KB Output is correct
8 Correct 176 ms 376796 KB Output is correct
9 Correct 186 ms 377292 KB Output is correct
10 Correct 190 ms 376468 KB Output is correct
11 Correct 175 ms 376696 KB Output is correct
12 Correct 196 ms 376648 KB Output is correct
13 Correct 352 ms 406276 KB Output is correct
14 Correct 310 ms 393592 KB Output is correct
15 Correct 251 ms 391448 KB Output is correct
16 Correct 256 ms 390384 KB Output is correct
17 Correct 687 ms 453300 KB Output is correct
18 Correct 481 ms 436780 KB Output is correct
19 Correct 367 ms 426572 KB Output is correct
20 Correct 387 ms 430084 KB Output is correct
21 Correct 684 ms 516904 KB Output is correct
22 Correct 1077 ms 597040 KB Output is correct
23 Correct 1063 ms 524500 KB Output is correct
24 Correct 631 ms 514868 KB Output is correct
25 Correct 1585 ms 621616 KB Output is correct
26 Correct 685 ms 485552 KB Output is correct
27 Correct 903 ms 549112 KB Output is correct
28 Correct 1802 ms 646852 KB Output is correct
29 Correct 1642 ms 633356 KB Output is correct
30 Correct 1388 ms 604540 KB Output is correct
31 Execution timed out 2124 ms 682036 KB Time limit exceeded
32 Correct 881 ms 551520 KB Output is correct