oj.uz

Submission #910640

# Submission time Handle Problem Language Result Execution time Memory
910640 2024-01-18T06:37:25 Z ByeWorld Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 2000 ms 311712 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<ll,ll> pii;
typedef pair<ll,pii> ipii;
vector <int> dx = {-1, 0, 0, 1};
vector <int> dy = {0, -1, 1, 0};

int h, w;
string s[4010];
bool 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;
        for(int i=0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(vis[nx][ny] || s[nx][ny] == '.') continue;
            if(s[nx][ny] == fnd){
                vec.pb({nx, ny});
                vis[nx][ny] = 1;
                cnt++;
            }
        }

        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 2063 ms 3292 KB Time limit exceeded
2 Execution timed out 2062 ms 604 KB Time limit exceeded
3 Execution timed out 2045 ms 604 KB Time limit exceeded
4 Execution timed out 2088 ms 4812 KB Time limit exceeded
5 Execution timed out 2020 ms 1880 KB Time limit exceeded
6 Execution timed out 2055 ms 604 KB Time limit exceeded
7 Execution timed out 2035 ms 600 KB Time limit exceeded
8 Execution timed out 2060 ms 860 KB Time limit exceeded
9 Execution timed out 2009 ms 856 KB Time limit exceeded
10 Execution timed out 2047 ms 1628 KB Time limit exceeded
11 Execution timed out 2041 ms 2520 KB Time limit exceeded
12 Execution timed out 2037 ms 2136 KB Time limit exceeded
13 Execution timed out 2013 ms 1880 KB Time limit exceeded
14 Execution timed out 2025 ms 2052 KB Time limit exceeded
15 Execution timed out 2073 ms 3164 KB Time limit exceeded
16 Execution timed out 2044 ms 3288 KB Time limit exceeded
17 Execution timed out 2040 ms 2908 KB Time limit exceeded
18 Execution timed out 2025 ms 4812 KB Time limit exceeded

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2020 ms 15448 KB Time limit exceeded
2 Execution timed out 2048 ms 8540 KB Time limit exceeded
3 Execution timed out 2063 ms 47816 KB Time limit exceeded
4 Execution timed out 2009 ms 15296 KB Time limit exceeded
5 Execution timed out 2061 ms 30184 KB Time limit exceeded
6 Execution timed out 2033 ms 111948 KB Time limit exceeded
7 Execution timed out 2054 ms 16220 KB Time limit exceeded
8 Execution timed out 2045 ms 15452 KB Time limit exceeded
9 Execution timed out 2036 ms 1112 KB Time limit exceeded
10 Execution timed out 2023 ms 600 KB Time limit exceeded
11 Execution timed out 2013 ms 15960 KB Time limit exceeded
12 Execution timed out 2058 ms 1116 KB Time limit exceeded
13 Execution timed out 2017 ms 8528 KB Time limit exceeded
14 Execution timed out 2064 ms 5980 KB Time limit exceeded
15 Execution timed out 2021 ms 6488 KB Time limit exceeded
16 Execution timed out 2061 ms 3456 KB Time limit exceeded
17 Execution timed out 2051 ms 16724 KB Time limit exceeded
18 Execution timed out 2047 ms 16212 KB Time limit exceeded
19 Execution timed out 2060 ms 15444 KB Time limit exceeded
20 Execution timed out 2055 ms 14164 KB Time limit exceeded
21 Execution timed out 2033 ms 31220 KB Time limit exceeded
22 Execution timed out 2027 ms 30316 KB Time limit exceeded
23 Execution timed out 2011 ms 26068 KB Time limit exceeded
24 Execution timed out 2045 ms 30844 KB Time limit exceeded
25 Execution timed out 2009 ms 47752 KB Time limit exceeded
26 Correct 492 ms 311712 KB Output is correct
27 Execution timed out 2098 ms 311684 KB Time limit exceeded
28 Execution timed out 2072 ms 110752 KB Time limit exceeded
29 Execution timed out 2007 ms 111776 KB Time limit exceeded
30 Execution timed out 2037 ms 311436 KB Time limit exceeded
31 Execution timed out 2045 ms 33800 KB Time limit exceeded
32 Execution timed out 2025 ms 47648 KB Time limit exceeded