oj.uz

Submission #42406

# Submission time Handle Problem Language Result Execution time Memory
42406 2018-02-26T17:26:51 Z Hassoony Tracks in the Snow (BOI13_tracks) C++14
36.5625 / 100
 2000 ms 1048576 KB 
#include<bits/stdc++.h>
#include<unordered_map>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double D;
const ll inf=(1ll<<61);
const ll mod=1e9+7;
const int MX=4002;
int n,m,cnt,h;
bool vis[MX][MX];
char a[MX][MX],c;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
vector<pair<int,int> >nodes;
void dfs(int x,int y){
    if(vis[x][y])return;
    vis[x][y]=1;
    cnt++;
    nodes.push_back({x,y});
    for(int i=0;i<4;i++){
        int nx=dx[i]+x,ny=dy[i]+y;
        if(nx>=n||ny>=m||nx<0||ny<0||a[nx][ny]!=a[x][y])continue;
        dfs(nx,ny);
    }
    a[x][y]=c;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%s",&a[i]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]!='.')h++;
        }
    }
    int ans=0;
    while(cnt!=h){
        c='R';
        if(a[0][0]=='R')c='F';
        cnt=0;
        dfs(0,0);
        ans++;
        for(auto pp:nodes)vis[pp.first][pp.second]=0;
        nodes.clear();
    }
    cout<<ans<<endl;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:31:41: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[4002]' [-Wformat=]
     for(int i=0;i<n;i++)scanf("%s",&a[i]);
                                         ^
tracks.cpp:30:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
tracks.cpp:31:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<n;i++)scanf("%s",&a[i]);
                                          ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 15076 KB Output is correct
2 Correct 2 ms 15076 KB Output is correct
3 Correct 3 ms 15076 KB Output is correct
4 Correct 40 ms 17616 KB Output is correct
5 Correct 67 ms 17616 KB Output is correct
6 Correct 2 ms 17616 KB Output is correct
7 Correct 3 ms 17616 KB Output is correct
8 Correct 4 ms 17616 KB Output is correct
9 Correct 5 ms 17616 KB Output is correct
10 Correct 101 ms 17616 KB Output is correct
11 Correct 10 ms 17616 KB Output is correct
12 Correct 78 ms 17616 KB Output is correct
13 Correct 63 ms 17616 KB Output is correct
14 Correct 65 ms 17616 KB Output is correct
15 Correct 588 ms 17616 KB Output is correct
16 Correct 275 ms 17616 KB Output is correct
17 Correct 452 ms 17616 KB Output is correct
18 Correct 38 ms 17776 KB Output is correct

Subtask #2
6.5625 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 31920 KB Time limit exceeded
2 Execution timed out 2050 ms 34280 KB Time limit exceeded
3 Execution timed out 2023 ms 34280 KB Time limit exceeded
4 Execution timed out 2057 ms 34280 KB Time limit exceeded
5 Execution timed out 2057 ms 34280 KB Time limit exceeded
6 Execution timed out 2082 ms 636484 KB Time limit exceeded
7 Execution timed out 2045 ms 636484 KB Time limit exceeded
8 Execution timed out 2029 ms 636484 KB Time limit exceeded
9 Correct 204 ms 636484 KB Output is correct
10 Correct 537 ms 636484 KB Output is correct
11 Correct 867 ms 636484 KB Output is correct
12 Execution timed out 2031 ms 636484 KB Time limit exceeded
13 Execution timed out 2053 ms 636484 KB Time limit exceeded
14 Execution timed out 2047 ms 636484 KB Time limit exceeded
15 Execution timed out 2049 ms 636484 KB Time limit exceeded
16 Execution timed out 2051 ms 636484 KB Time limit exceeded
17 Execution timed out 2055 ms 636484 KB Time limit exceeded
18 Execution timed out 2035 ms 636484 KB Time limit exceeded
19 Execution timed out 2067 ms 636484 KB Time limit exceeded
20 Execution timed out 2041 ms 636484 KB Time limit exceeded
21 Execution timed out 2047 ms 636484 KB Time limit exceeded
22 Execution timed out 2049 ms 636484 KB Time limit exceeded
23 Execution timed out 2051 ms 636484 KB Time limit exceeded
24 Execution timed out 2043 ms 636484 KB Time limit exceeded
25 Execution timed out 2054 ms 636484 KB Time limit exceeded
26 Execution timed out 2151 ms 1048576 KB Time limit exceeded
27 Execution timed out 2098 ms 1048576 KB Time limit exceeded
28 Execution timed out 2088 ms 1048576 KB Time limit exceeded
29 Execution timed out 2100 ms 1048576 KB Time limit exceeded
30 Execution timed out 2099 ms 1048576 KB Time limit exceeded
31 Execution timed out 2069 ms 1048576 KB Time limit exceeded
32 Execution timed out 2105 ms 1048576 KB Time limit exceeded