oj.uz

Submission #631273

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

const int N=4000;
int n, m;
string grid[N];
int par[N*N], rnk[N*N];
int dx[]={0, 0, 1, -1};
int 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;
                adj[find(m*i+j)].push_back(find(m*x+y));
                adj[find(m*x+y)].push_back(find(m*i+j));
            }
        }
    }

    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 236 ms 384580 KB Output is correct
2 Correct 166 ms 376104 KB Output is correct
3 Correct 174 ms 376140 KB Output is correct
4 Correct 184 ms 379084 KB Output is correct
5 Correct 180 ms 377536 KB Output is correct
6 Correct 167 ms 376124 KB Output is correct
7 Correct 169 ms 376220 KB Output is correct
8 Correct 172 ms 376268 KB Output is correct
9 Correct 176 ms 376324 KB Output is correct
10 Correct 178 ms 377456 KB Output is correct
11 Correct 176 ms 376860 KB Output is correct
12 Correct 188 ms 379096 KB Output is correct
13 Correct 177 ms 377580 KB Output is correct
14 Correct 179 ms 377484 KB Output is correct
15 Correct 212 ms 383292 KB Output is correct
16 Correct 233 ms 384556 KB Output is correct
17 Correct 210 ms 381264 KB Output is correct
18 Correct 186 ms 379016 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 377036 KB Output is correct
2 Correct 542 ms 409120 KB Output is correct
3 Correct 1002 ms 620684 KB Output is correct
4 Correct 373 ms 433740 KB Output is correct
5 Correct 953 ms 597092 KB Output is correct
6 Correct 1887 ms 678104 KB Output is correct
7 Correct 170 ms 376780 KB Output is correct
8 Correct 180 ms 376904 KB Output is correct
9 Correct 187 ms 377416 KB Output is correct
10 Correct 185 ms 376576 KB Output is correct
11 Correct 183 ms 376720 KB Output is correct
12 Correct 177 ms 376704 KB Output is correct
13 Correct 339 ms 409072 KB Output is correct
14 Correct 283 ms 395304 KB Output is correct
15 Correct 255 ms 393380 KB Output is correct
16 Correct 255 ms 391628 KB Output is correct
17 Correct 571 ms 458604 KB Output is correct
18 Correct 474 ms 444544 KB Output is correct
19 Correct 368 ms 433760 KB Output is correct
20 Correct 364 ms 433368 KB Output is correct
21 Correct 657 ms 522468 KB Output is correct
22 Correct 946 ms 597144 KB Output is correct
23 Correct 964 ms 532568 KB Output is correct
24 Correct 619 ms 520892 KB Output is correct
25 Correct 1542 ms 652948 KB Output is correct
26 Correct 736 ms 485592 KB Output is correct
27 Correct 901 ms 557576 KB Output is correct
28 Correct 1822 ms 678244 KB Output is correct
29 Correct 1715 ms 664716 KB Output is correct
30 Correct 1410 ms 627668 KB Output is correct
31 Execution timed out 2114 ms 702128 KB Time limit exceeded
32 Correct 930 ms 561832 KB Output is correct