oj.uz

Submission #631276

# Submission time Handle Problem Language Result Execution time Memory
631276 2022-08-18T02:21:45 Z czhang2718 Tracks in the Snow (BOI13_tracks) C++17
89.0625 / 100
 2000 ms 662016 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);
    par[a]=b;
    // 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 247 ms 383688 KB Output is correct
2 Correct 167 ms 376108 KB Output is correct
3 Correct 175 ms 376128 KB Output is correct
4 Correct 207 ms 378392 KB Output is correct
5 Correct 184 ms 377168 KB Output is correct
6 Correct 166 ms 376156 KB Output is correct
7 Correct 175 ms 376132 KB Output is correct
8 Correct 202 ms 376196 KB Output is correct
9 Correct 171 ms 376284 KB Output is correct
10 Correct 178 ms 377180 KB Output is correct
11 Correct 214 ms 376692 KB Output is correct
12 Correct 192 ms 378828 KB Output is correct
13 Correct 171 ms 377252 KB Output is correct
14 Correct 176 ms 377204 KB Output is correct
15 Correct 229 ms 382284 KB Output is correct
16 Correct 228 ms 383632 KB Output is correct
17 Correct 202 ms 380368 KB Output is correct
18 Correct 201 ms 378508 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 376732 KB Output is correct
2 Correct 357 ms 403132 KB Output is correct
3 Correct 976 ms 590252 KB Output is correct
4 Correct 362 ms 419252 KB Output is correct
5 Correct 955 ms 597244 KB Output is correct
6 Execution timed out 2109 ms 552104 KB Time limit exceeded
7 Correct 175 ms 376612 KB Output is correct
8 Correct 170 ms 376652 KB Output is correct
9 Correct 176 ms 377148 KB Output is correct
10 Correct 188 ms 376484 KB Output is correct
11 Correct 182 ms 376688 KB Output is correct
12 Correct 178 ms 376628 KB Output is correct
13 Correct 328 ms 403368 KB Output is correct
14 Correct 266 ms 391844 KB Output is correct
15 Correct 251 ms 389452 KB Output is correct
16 Correct 275 ms 389252 KB Output is correct
17 Correct 574 ms 445332 KB Output is correct
18 Correct 476 ms 428932 KB Output is correct
19 Correct 364 ms 419244 KB Output is correct
20 Correct 358 ms 423412 KB Output is correct
21 Correct 634 ms 501452 KB Output is correct
22 Correct 902 ms 596940 KB Output is correct
23 Correct 954 ms 510668 KB Output is correct
24 Correct 598 ms 504012 KB Output is correct
25 Correct 1500 ms 590412 KB Output is correct
26 Correct 1168 ms 485456 KB Output is correct
27 Correct 1642 ms 525164 KB Output is correct
28 Execution timed out 2114 ms 551928 KB Time limit exceeded
29 Execution timed out 2065 ms 539056 KB Time limit exceeded
30 Execution timed out 2057 ms 574692 KB Time limit exceeded
31 Execution timed out 2073 ms 662016 KB Time limit exceeded
32 Correct 1472 ms 528312 KB Output is correct