oj.uz

Submission #101447

# Submission time Handle Problem Language Result Execution time Memory
101447 2019-03-19T02:16:15 Z jamielim Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 2000 ms 1049600 KB 
#include <bits/stdc++.h>
using namespace std;

int h,w;
set<int> adj[16000000];
int vis[16000000];
int dist[16000000];
int cnt=0;
void dfs(int x){
    if(vis[x]==1)return;
    vis[x]=1;
    for(set<int>::iterator it=adj[x].begin();it!=adj[x].end();++it){
        int i=(*it);
        if(vis[i]==1)continue;
        if(dist[i]<dist[x]+1){
            dist[i]=dist[x]+1;
            dfs(i);
        }else if(vis[i]==0){
            dfs(i);
        }
    }
    vis[x]=2;
}

int main(){
    scanf("%d%d",&h,&w);
    char grid[h+5][w+5];
    for(int i=0;i<h;i++){
        scanf("%s",grid[i]);
    }
    queue<pair<int,int> > q;
    int com[h][w];
    memset(com,-1,sizeof(com));
    int c=0;
    int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(com[i][j]==-1){
                q.push(make_pair(i,j));
                com[i][j]=c;
                while(!q.empty()){
                    pair<int,int> cur=q.front();q.pop();
                    for(int k=0;k<4;k++){
                        int nx=cur.first+dx[k],ny=cur.second+dy[k];
                        if(nx<0||ny<0||nx>=h||ny>=w)continue;
                        if(grid[nx][ny]==grid[cur.first][cur.second]&&com[nx][ny]==-1){
                            com[nx][ny]=c;
                            q.push(make_pair(nx,ny));
                        }
                    }
                }
                c++;
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            for(int k=0;k<4;k++){
                int nx=i+dx[k],ny=j+dy[k];
                if(0<=nx&&nx<h&&0<=ny&&ny<w){
                    if(com[i][j]!=com[nx][ny]){
                        adj[com[i][j]].insert(com[nx][ny]);
                    }
                }
            }
        }
    }
    memset(dist,-1,sizeof(dist));
    dist[0]=0;
    dfs(0);
    int ans=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(grid[i][j]=='.'){
                ans=max(ans,dist[com[i][j]]);
            }
        }
    }
    printf("%d",ans);
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&h,&w);
     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",grid[i]);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1261 ms 822184 KB Output isn't correct
2 Incorrect 822 ms 814760 KB Output isn't correct
3 Incorrect 740 ms 814676 KB Output isn't correct
4 Incorrect 788 ms 815680 KB Output isn't correct
5 Incorrect 787 ms 817336 KB Output isn't correct
6 Incorrect 807 ms 814456 KB Output isn't correct
7 Incorrect 816 ms 814572 KB Output isn't correct
8 Incorrect 843 ms 814580 KB Output isn't correct
9 Incorrect 804 ms 814700 KB Output isn't correct
10 Incorrect 770 ms 816564 KB Output isn't correct
11 Incorrect 774 ms 814652 KB Output isn't correct
12 Incorrect 805 ms 817460 KB Output isn't correct
13 Incorrect 816 ms 817272 KB Output isn't correct
14 Incorrect 845 ms 817272 KB Output isn't correct
15 Incorrect 899 ms 822956 KB Output isn't correct
16 Incorrect 879 ms 822164 KB Output isn't correct
17 Incorrect 873 ms 826692 KB Output isn't correct
18 Incorrect 826 ms 815652 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 762 ms 816340 KB Output isn't correct
2 Incorrect 1079 ms 867284 KB Output isn't correct
3 Execution timed out 2154 ms 924400 KB Time limit exceeded
4 Incorrect 1643 ms 910780 KB Output isn't correct
5 Execution timed out 2139 ms 1046092 KB Time limit exceeded
6 Execution timed out 2112 ms 866348 KB Time limit exceeded
7 Incorrect 830 ms 816104 KB Output isn't correct
8 Incorrect 927 ms 816468 KB Output isn't correct
9 Incorrect 878 ms 816196 KB Output isn't correct
10 Incorrect 796 ms 815248 KB Output isn't correct
11 Incorrect 790 ms 815224 KB Output isn't correct
12 Incorrect 836 ms 817984 KB Output isn't correct
13 Incorrect 1166 ms 867432 KB Output isn't correct
14 Incorrect 1016 ms 845488 KB Output isn't correct
15 Incorrect 1308 ms 859296 KB Output isn't correct
16 Incorrect 930 ms 837240 KB Output isn't correct
17 Incorrect 1610 ms 953840 KB Output isn't correct
18 Execution timed out 2127 ms 999288 KB Time limit exceeded
19 Incorrect 1446 ms 910976 KB Output isn't correct
20 Incorrect 1274 ms 905800 KB Output isn't correct
21 Execution timed out 2108 ms 1034284 KB Time limit exceeded
22 Runtime error 1939 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Execution timed out 2100 ms 1043600 KB Time limit exceeded
24 Execution timed out 2089 ms 1049600 KB Time limit exceeded
25 Execution timed out 2119 ms 932824 KB Time limit exceeded
26 Execution timed out 2040 ms 880000 KB Time limit exceeded
27 Incorrect 1973 ms 899944 KB Output isn't correct
28 Execution timed out 2089 ms 861824 KB Time limit exceeded
29 Execution timed out 2123 ms 858052 KB Time limit exceeded
30 Execution timed out 2118 ms 852972 KB Time limit exceeded
31 Execution timed out 2178 ms 920136 KB Time limit exceeded
32 Execution timed out 2069 ms 928684 KB Time limit exceeded