oj.uz

Submission #910651

# Submission time Handle Problem Language Result Execution time Memory
910651 2024-01-18T06:46:53 Z ByeWorld Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 2000 ms 220608 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
//#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e5+5;
const int MAXK = 205;
const int LOG = 20;
const int MOD = 1e9+7;
const int SQRT = 520;
const int INF = 1e9+10;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
vector <int> dx = {-1, 0, 0, 1};
vector <int> dy = {0, -1, 1, 0};

int h, w;
string s[4010];
int vis[4010][4010];

int ans, cnt, tot;
vector <pii> vec;
char fnd;
void bfs(){
    int siz = vec.size();
    for(int j=0; j<siz; j++){
        int x = vec[j].fi, y = vec[j].se;
        if(vis[x][y]==2) continue;

        bool te = 0;
        for(int i=0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(vis[nx][ny] || s[nx][ny] == '.') continue;
            te = 1;
            if(s[nx][ny] == fnd){
                vec.pb({nx, ny});
                vis[nx][ny] = 1;
                cnt++;
            }
        }
        if(!te) vis[x][y] = 2;


        siz = vec.size();
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> h >> w;
    for(int i=1; i<=h; i++){
        cin >> s[i];
        s[i] = '.'+s[i]+'.';
        for(int j=1; j<=w; j++)
            if(s[i][j]!='.') tot++;
    }
    //cout << tot << " t\n";
    for(int i=0; i<=w+1; i++){
        s[0] += '.'; s[h+1] += '.';
    }

    fnd = s[1][1]; vec.pb({1, 1}); vis[1][1] = 1; 
    cnt = 1;
    while(cnt != tot){
        ans++;
        bfs();
        // if(fnd='F'){
        //     for(auto in : vec) cout << in.fi << ' '<< in.se << " p\n";
        //     exit(0);
        // }
        if(fnd=='R') fnd = 'H';
        else fnd = 'R';
    } 
    cout << ans << '\n';
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 3420 KB Time limit exceeded
2 Execution timed out 2012 ms 604 KB Time limit exceeded
3 Execution timed out 2063 ms 604 KB Time limit exceeded
4 Execution timed out 2059 ms 4760 KB Time limit exceeded
5 Execution timed out 2063 ms 1884 KB Time limit exceeded
6 Execution timed out 2048 ms 604 KB Time limit exceeded
7 Execution timed out 2066 ms 604 KB Time limit exceeded
8 Execution timed out 2054 ms 860 KB Time limit exceeded
9 Execution timed out 2020 ms 856 KB Time limit exceeded
10 Execution timed out 2056 ms 1628 KB Time limit exceeded
11 Execution timed out 2063 ms 2264 KB Time limit exceeded
12 Execution timed out 2044 ms 1884 KB Time limit exceeded
13 Execution timed out 2021 ms 1880 KB Time limit exceeded
14 Execution timed out 2012 ms 1880 KB Time limit exceeded
15 Execution timed out 2052 ms 3164 KB Time limit exceeded
16 Execution timed out 2067 ms 3420 KB Time limit exceeded
17 Execution timed out 2033 ms 2904 KB Time limit exceeded
18 Execution timed out 2055 ms 4560 KB Time limit exceeded

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2031 ms 15964 KB Time limit exceeded
2 Execution timed out 2041 ms 8796 KB Time limit exceeded
3 Execution timed out 2055 ms 48304 KB Time limit exceeded
4 Execution timed out 2047 ms 15708 KB Time limit exceeded
5 Execution timed out 2043 ms 30292 KB Time limit exceeded
6 Execution timed out 2013 ms 99740 KB Time limit exceeded
7 Execution timed out 2008 ms 16728 KB Time limit exceeded
8 Execution timed out 2071 ms 15964 KB Time limit exceeded
9 Execution timed out 2025 ms 856 KB Time limit exceeded
10 Execution timed out 2087 ms 600 KB Time limit exceeded
11 Execution timed out 2050 ms 16220 KB Time limit exceeded
12 Execution timed out 2041 ms 1112 KB Time limit exceeded
13 Execution timed out 2036 ms 8796 KB Time limit exceeded
14 Execution timed out 2021 ms 5976 KB Time limit exceeded
15 Execution timed out 2033 ms 6488 KB Time limit exceeded
16 Execution timed out 2029 ms 3416 KB Time limit exceeded
17 Execution timed out 2055 ms 16732 KB Time limit exceeded
18 Execution timed out 2071 ms 16476 KB Time limit exceeded
19 Execution timed out 2048 ms 15708 KB Time limit exceeded
20 Execution timed out 2059 ms 14428 KB Time limit exceeded
21 Execution timed out 2044 ms 31324 KB Time limit exceeded
22 Execution timed out 2029 ms 30292 KB Time limit exceeded
23 Execution timed out 2052 ms 26200 KB Time limit exceeded
24 Execution timed out 2041 ms 31056 KB Time limit exceeded
25 Execution timed out 2041 ms 48208 KB Time limit exceeded
26 Correct 364 ms 202656 KB Output is correct
27 Execution timed out 2087 ms 220608 KB Time limit exceeded
28 Execution timed out 2053 ms 99748 KB Time limit exceeded
29 Execution timed out 2062 ms 104868 KB Time limit exceeded
30 Execution timed out 2021 ms 219056 KB Time limit exceeded
31 Execution timed out 2053 ms 34252 KB Time limit exceeded
32 Execution timed out 2019 ms 48344 KB Time limit exceeded