oj.uz

Submission #520163

# Submission time Handle Problem Language Result Execution time Memory
520163 2022-01-28T15:57:32 Z krit3379 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1733 ms 759112 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 4005
#define K 6000000

struct A{
    int x,y;
};

int sz,a[N][N],di[4]={1,-1,0,0},dj[4]={0,0,1,-1};
char s[N][N];
bitset<N> vis[N];
bitset<K> ch;
queue<A> q;
set<int> se[K];

int main(){
    int n,m,i,j,k,x,y,num;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf(" %s",s[i]+1);
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(s[i][j]=='.'||vis[i][j])continue;
            q.push({i,j});
            vis[i][j]=true;
            a[i][j]=++sz;
            while(!q.empty()){
                x=q.front().x;
                y=q.front().y;
                q.pop();
                a[x][y]=sz;
                for(k=0;k<4;k++){
                    int X=x+di[k],Y=y+dj[k];
                    if(X>0&&X<=n&&Y>0&&Y<=m&&s[x][y]==s[X][Y]&&!vis[X][Y])q.push({X,Y}),vis[X][Y]=true;
                    else if(X>0&&X<=n&&Y>0&&Y<=m&&s[x][y]!=s[X][Y]&&s[X][Y]!='.'&&a[X][Y])se[a[x][y]].insert(a[X][Y]),se[a[X][Y]].insert(a[x][y]);
                }
            }
        }
    }
    q.push({a[1][1],1});
    ch[a[1][1]]=true;
    while(!q.empty()){
        x=q.front().x;
        y=q.front().y;
        q.pop();
        for(auto num:se[x])if(!ch[num])ch[num]=true,q.push({num,y+1});
    }
    printf("%d",y);
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:18:23: warning: unused variable 'num' [-Wunused-variable]
   18 |     int n,m,i,j,k,x,y,num;
      |                       ^~~
tracks.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
tracks.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf(" %s",s[i]+1);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 292520 KB Output is correct
2 Correct 123 ms 282224 KB Output is correct
3 Correct 133 ms 282536 KB Output is correct
4 Correct 151 ms 287212 KB Output is correct
5 Correct 127 ms 285680 KB Output is correct
6 Correct 125 ms 282292 KB Output is correct
7 Correct 151 ms 282480 KB Output is correct
8 Correct 123 ms 282600 KB Output is correct
9 Correct 136 ms 282928 KB Output is correct
10 Correct 125 ms 285212 KB Output is correct
11 Correct 141 ms 284024 KB Output is correct
12 Correct 167 ms 286788 KB Output is correct
13 Correct 125 ms 285756 KB Output is correct
14 Correct 132 ms 285808 KB Output is correct
15 Correct 156 ms 291904 KB Output is correct
16 Correct 166 ms 292600 KB Output is correct
17 Correct 150 ms 291568 KB Output is correct
18 Correct 144 ms 287204 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 314996 KB Output is correct
2 Correct 247 ms 319472 KB Output is correct
3 Correct 672 ms 506412 KB Output is correct
4 Correct 267 ms 341956 KB Output is correct
5 Correct 870 ms 759112 KB Output is correct
6 Correct 1367 ms 433424 KB Output is correct
7 Correct 138 ms 316320 KB Output is correct
8 Correct 134 ms 314936 KB Output is correct
9 Correct 126 ms 283156 KB Output is correct
10 Correct 136 ms 282420 KB Output is correct
11 Correct 133 ms 315496 KB Output is correct
12 Correct 124 ms 284464 KB Output is correct
13 Correct 240 ms 319484 KB Output is correct
14 Correct 194 ms 305540 KB Output is correct
15 Correct 184 ms 308780 KB Output is correct
16 Correct 189 ms 298356 KB Output is correct
17 Correct 388 ms 368476 KB Output is correct
18 Correct 342 ms 370440 KB Output is correct
19 Correct 437 ms 341820 KB Output is correct
20 Correct 248 ms 342340 KB Output is correct
21 Correct 441 ms 425016 KB Output is correct
22 Correct 906 ms 759104 KB Output is correct
23 Correct 653 ms 436776 KB Output is correct
24 Correct 504 ms 473852 KB Output is correct
25 Correct 1240 ms 592196 KB Output is correct
26 Correct 658 ms 364420 KB Output is correct
27 Correct 807 ms 379760 KB Output is correct
28 Correct 1304 ms 433352 KB Output is correct
29 Correct 1346 ms 410228 KB Output is correct
30 Correct 1119 ms 399108 KB Output is correct
31 Correct 1733 ms 572788 KB Output is correct
32 Correct 791 ms 391408 KB Output is correct