oj.uz

Submission #631293

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

const int N=4000;
int n, m;
short dx[]={0, 0, 1, -1};
short dy[]={1, -1, 0, 0};
vector<int> adj[N*N+1];
short grid[N][N];
int cmp[N][N];

void dfs(int u, int c){
    cmp[u/m][u%m]=c;
    int i=u/m;
    int j=u%m;
    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] || cmp[x][y]) continue;
        dfs(m*x+y, c);
    }
}

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);
        }
    }

    int c=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(grid[i][j]==0 || cmp[i][j]) continue;
            dfs(m*i+j, ++c);
        }
    }

    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;
                adj[cmp[i][j]].push_back(cmp[x][y]);
                adj[cmp[x][y]].push_back(cmp[i][j]);
            }
        }
    }

    queue<int> q;
    int r=cmp[0][0];
    q.push(r);
    vector<int> vis(c+1);
    for(; !q.empty(); q.pop()){
        int x=q.front();
        for(int k:adj[x]){
            if(!vis[k] && k!=r){
                vis[k]=vis[x]+1;
                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 217 ms 387016 KB Output is correct
2 Correct 170 ms 376304 KB Output is correct
3 Correct 172 ms 376384 KB Output is correct
4 Correct 214 ms 382748 KB Output is correct
5 Correct 177 ms 379156 KB Output is correct
6 Correct 169 ms 376156 KB Output is correct
7 Correct 177 ms 376424 KB Output is correct
8 Correct 173 ms 376608 KB Output is correct
9 Correct 171 ms 376912 KB Output is correct
10 Correct 181 ms 378828 KB Output is correct
11 Correct 184 ms 378520 KB Output is correct
12 Correct 200 ms 380888 KB Output is correct
13 Correct 178 ms 379232 KB Output is correct
14 Correct 177 ms 379144 KB Output is correct
15 Correct 219 ms 385472 KB Output is correct
16 Correct 223 ms 387128 KB Output is correct
17 Correct 225 ms 383548 KB Output is correct
18 Correct 183 ms 382744 KB Output is correct

Subtask #2
65.625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 407500 KB Output is correct
2 Correct 546 ms 406572 KB Output is correct
3 Correct 984 ms 526324 KB Output is correct
4 Correct 392 ms 423244 KB Output is correct
5 Correct 1076 ms 590700 KB Output is correct
6 Correct 1550 ms 603924 KB Output is correct
7 Correct 184 ms 409036 KB Output is correct
8 Correct 186 ms 407548 KB Output is correct
9 Correct 175 ms 377164 KB Output is correct
10 Correct 173 ms 376528 KB Output is correct
11 Correct 184 ms 407992 KB Output is correct
12 Correct 175 ms 377804 KB Output is correct
13 Correct 359 ms 406488 KB Output is correct
14 Correct 243 ms 395512 KB Output is correct
15 Correct 239 ms 395040 KB Output is correct
16 Correct 259 ms 390164 KB Output is correct
17 Correct 533 ms 443844 KB Output is correct
18 Correct 474 ms 435156 KB Output is correct
19 Correct 355 ms 423164 KB Output is correct
20 Correct 372 ms 422984 KB Output is correct
21 Correct 671 ms 477772 KB Output is correct
22 Correct 1043 ms 590584 KB Output is correct
23 Correct 905 ms 491472 KB Output is correct
24 Correct 696 ms 481824 KB Output is correct
25 Correct 1418 ms 550788 KB Output is correct
26 Runtime error 619 ms 1048576 KB Execution killed with signal 9
27 Correct 1094 ms 696296 KB Output is correct
28 Correct 1524 ms 603868 KB Output is correct
29 Correct 1454 ms 581708 KB Output is correct
30 Correct 1296 ms 638188 KB Output is correct
31 Execution timed out 2056 ms 692048 KB Time limit exceeded
32 Correct 1041 ms 817880 KB Output is correct