oj.uz

Submission #631272

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

const int N=4000;
int n, m;
string grid[N];
int par[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);
    par[a]=b;
}

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
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 235 ms 384220 KB Output isn't correct
2 Incorrect 167 ms 376184 KB Output isn't correct
3 Incorrect 177 ms 376396 KB Output isn't correct
4 Correct 188 ms 378632 KB Output is correct
5 Incorrect 181 ms 377968 KB Output isn't correct
6 Incorrect 188 ms 376316 KB Output isn't correct
7 Incorrect 170 ms 376248 KB Output isn't correct
8 Correct 171 ms 376392 KB Output is correct
9 Incorrect 176 ms 376268 KB Output isn't correct
10 Incorrect 188 ms 377816 KB Output isn't correct
11 Correct 174 ms 376688 KB Output is correct
12 Incorrect 188 ms 379080 KB Output isn't correct
13 Incorrect 189 ms 378032 KB Output isn't correct
14 Incorrect 179 ms 377912 KB Output isn't correct
15 Incorrect 233 ms 383860 KB Output isn't correct
16 Incorrect 264 ms 384296 KB Output isn't correct
17 Incorrect 224 ms 382952 KB Output isn't correct
18 Correct 186 ms 378552 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 191 ms 377256 KB Output isn't correct
2 Incorrect 475 ms 416300 KB Output isn't correct
3 Execution timed out 2086 ms 636448 KB Time limit exceeded
4 Incorrect 795 ms 443664 KB Output isn't correct
5 Execution timed out 2056 ms 728356 KB Time limit exceeded
6 Execution timed out 2122 ms 567452 KB Time limit exceeded
7 Incorrect 174 ms 377148 KB Output isn't correct
8 Incorrect 202 ms 377156 KB Output isn't correct
9 Incorrect 181 ms 377708 KB Output isn't correct
10 Incorrect 170 ms 377052 KB Output isn't correct
11 Incorrect 174 ms 377012 KB Output isn't correct
12 Incorrect 173 ms 377136 KB Output isn't correct
13 Incorrect 456 ms 416392 KB Output isn't correct
14 Incorrect 353 ms 399528 KB Output isn't correct
15 Incorrect 386 ms 401332 KB Output isn't correct
16 Incorrect 337 ms 394220 KB Output isn't correct
17 Incorrect 958 ms 479992 KB Output isn't correct
18 Incorrect 1053 ms 474716 KB Output isn't correct
19 Incorrect 769 ms 443664 KB Output isn't correct
20 Incorrect 870 ms 448300 KB Output isn't correct
21 Execution timed out 2049 ms 567624 KB Time limit exceeded
22 Execution timed out 2064 ms 728468 KB Time limit exceeded
23 Incorrect 1734 ms 576092 KB Output isn't correct
24 Execution timed out 2047 ms 584896 KB Time limit exceeded
25 Execution timed out 2132 ms 651812 KB Time limit exceeded
26 Correct 1196 ms 497384 KB Output is correct
27 Correct 1709 ms 540780 KB Output is correct
28 Execution timed out 2107 ms 567640 KB Time limit exceeded
29 Execution timed out 2106 ms 554660 KB Time limit exceeded
30 Execution timed out 2093 ms 528116 KB Time limit exceeded
31 Execution timed out 2037 ms 674296 KB Time limit exceeded
32 Incorrect 1800 ms 552328 KB Output isn't correct