oj.uz

Submission #631283

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

const int N=4000;
int n, m;
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];
short grid[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++){
            char c; cin >> c;
            grid[i][j]=(c=='F'?2:c=='R'?1:0);
            par[i*m+j]=i*m+j;
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(grid[i][j]==0) 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]==0) 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]==0) 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 215 ms 386176 KB Output is correct
2 Correct 165 ms 376104 KB Output is correct
3 Correct 165 ms 376268 KB Output is correct
4 Correct 182 ms 380808 KB Output is correct
5 Correct 178 ms 378452 KB Output is correct
6 Correct 165 ms 376088 KB Output is correct
7 Correct 168 ms 376316 KB Output is correct
8 Correct 168 ms 376320 KB Output is correct
9 Correct 174 ms 376540 KB Output is correct
10 Correct 197 ms 378264 KB Output is correct
11 Correct 178 ms 377516 KB Output is correct
12 Correct 197 ms 380236 KB Output is correct
13 Correct 174 ms 378536 KB Output is correct
14 Correct 176 ms 378432 KB Output is correct
15 Correct 210 ms 384972 KB Output is correct
16 Correct 220 ms 386152 KB Output is correct
17 Correct 201 ms 382956 KB Output is correct
18 Correct 190 ms 380776 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 391996 KB Output is correct
2 Correct 318 ms 412292 KB Output is correct
3 Correct 1026 ms 594060 KB Output is correct
4 Correct 383 ms 437200 KB Output is correct
5 Correct 1004 ms 599176 KB Output is correct
6 Correct 1644 ms 660472 KB Output is correct
7 Correct 175 ms 392592 KB Output is correct
8 Correct 176 ms 392020 KB Output is correct
9 Correct 178 ms 377208 KB Output is correct
10 Correct 167 ms 376368 KB Output is correct
11 Correct 177 ms 392484 KB Output is correct
12 Correct 172 ms 377180 KB Output is correct
13 Correct 319 ms 412384 KB Output is correct
14 Correct 258 ms 397960 KB Output is correct
15 Correct 253 ms 396228 KB Output is correct
16 Correct 242 ms 392472 KB Output is correct
17 Correct 562 ms 462140 KB Output is correct
18 Correct 485 ms 448204 KB Output is correct
19 Correct 406 ms 437164 KB Output is correct
20 Correct 391 ms 436560 KB Output is correct
21 Correct 689 ms 515524 KB Output is correct
22 Correct 987 ms 599156 KB Output is correct
23 Correct 923 ms 527308 KB Output is correct
24 Correct 681 ms 512000 KB Output is correct
25 Correct 1596 ms 635404 KB Output is correct
26 Correct 812 ms 451620 KB Output is correct
27 Correct 1070 ms 533912 KB Output is correct
28 Correct 1650 ms 660484 KB Output is correct
29 Correct 1552 ms 646908 KB Output is correct
30 Correct 1622 ms 609644 KB Output is correct
31 Execution timed out 2115 ms 735872 KB Time limit exceeded
32 Correct 1032 ms 538636 KB Output is correct