oj.uz

Submission #631280

# Submission time Handle Problem Language Result Execution time Memory
631280 2022-08-18T02:27:34 Z czhang2718 Tracks in the Snow (BOI13_tracks) C++17
78.125 / 100
 2000 ms 716100 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];
short 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);
            }
        }
    }
    short 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 220 ms 385740 KB Output is correct
2 Correct 174 ms 376160 KB Output is correct
3 Correct 176 ms 376320 KB Output is correct
4 Correct 186 ms 380388 KB Output is correct
5 Correct 179 ms 378348 KB Output is correct
6 Correct 168 ms 376156 KB Output is correct
7 Correct 176 ms 376268 KB Output is correct
8 Correct 173 ms 376316 KB Output is correct
9 Correct 171 ms 376572 KB Output is correct
10 Correct 178 ms 378228 KB Output is correct
11 Correct 184 ms 377380 KB Output is correct
12 Correct 187 ms 379956 KB Output is correct
13 Correct 178 ms 378384 KB Output is correct
14 Correct 190 ms 378268 KB Output is correct
15 Correct 232 ms 384576 KB Output is correct
16 Correct 220 ms 385712 KB Output is correct
17 Correct 204 ms 382516 KB Output is correct
18 Correct 184 ms 380488 KB Output is correct

Subtask #2
48.125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 391836 KB Output is correct
2 Correct 346 ms 409524 KB Output is correct
3 Incorrect 1070 ms 586076 KB Output isn't correct
4 Correct 403 ms 429896 KB Output is correct
5 Incorrect 1033 ms 590320 KB Output isn't correct
6 Correct 1734 ms 629128 KB Output is correct
7 Correct 183 ms 392608 KB Output is correct
8 Correct 199 ms 392060 KB Output is correct
9 Correct 174 ms 377128 KB Output is correct
10 Correct 175 ms 376376 KB Output is correct
11 Correct 183 ms 392224 KB Output is correct
12 Correct 174 ms 377168 KB Output is correct
13 Correct 323 ms 409424 KB Output is correct
14 Correct 255 ms 396244 KB Output is correct
15 Incorrect 266 ms 394384 KB Output isn't correct
16 Correct 242 ms 391308 KB Output is correct
17 Correct 808 ms 456628 KB Output is correct
18 Incorrect 500 ms 440304 KB Output isn't correct
19 Correct 396 ms 429836 KB Output is correct
20 Incorrect 406 ms 433304 KB Output isn't correct
21 Incorrect 689 ms 510128 KB Output isn't correct
22 Incorrect 1026 ms 590300 KB Output isn't correct
23 Correct 948 ms 519516 KB Output is correct
24 Incorrect 762 ms 506016 KB Output isn't correct
25 Incorrect 1629 ms 603824 KB Output isn't correct
26 Correct 832 ms 451452 KB Output is correct
27 Correct 1110 ms 524288 KB Output is correct
28 Correct 1732 ms 629020 KB Output is correct
29 Correct 1570 ms 615508 KB Output is correct
30 Correct 1427 ms 586260 KB Output is correct
31 Execution timed out 2095 ms 716100 KB Time limit exceeded
32 Correct 1046 ms 527180 KB Output is correct