oj.uz

Submission #988917

# Submission time Handle Problem Language Result Execution time Memory
988917 2024-05-26T18:27:48 Z IvanYamasaki Tracks in the Snow (BOI13_tracks) C++17
51.875 / 100
 2000 ms 829416 KB 
#include <bits/stdc++.h>
using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define pii pair<int , int>
#define vi vector<int>
#define pb push_back
#define f first
#define s second
#define ll long long
#define grid vector<vector<int>>

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 1e5+10;

int h,w; 
grid g;
int isR=0, isF=0, ans=1; 

pii moves[] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

bool valid(pii coord, int a){
    int x=coord.f, y=coord.s;
    return x>=0 and x<h and y>=0 and y<w and g[x][y]==a;
}

void dfs(pii src, int a){

    for(pii i : moves){
        int x = src.f+i.f, y=src.s+i.s; 
        if(valid({x,y}, a)) {
            if(g[x][y]==1) {
                if(isR!=0) g[x][y]=2; else g[x][y]=0;
                isF--; isR++;
            }
            else if(g[x][y]==2){
                if(isF!=0) g[x][y]=1; else g[x][y]=0;
                isR--; isF++;
            } 
            dfs({x,y}, a);
        }
    } 
}

int main(){ _

    cin>>h>>w; g.resize(h, vi(w));
    for(int i=0; i<h; i++) for(int j=0; j<w; j++){
        char c; cin >>c;
        if(c=='.') g[i][j]=0;
        else if(c=='F'){ g[i][j]=1; isF++; }
        else if(c=='R'){ g[i][j]=2; isR++; }
    }
    while(isR!=0 and isF!=0){
        ans++; dfs({h-1,w-1}, g[h-1][w-1]);
    }

    cout << ans << endl;

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 11092 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 12 ms 8008 KB Output is correct
5 Correct 27 ms 1112 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 24 ms 1116 KB Output is correct
11 Correct 3 ms 2188 KB Output is correct
12 Correct 24 ms 3676 KB Output is correct
13 Correct 27 ms 1116 KB Output is correct
14 Correct 27 ms 1096 KB Output is correct
15 Correct 148 ms 3152 KB Output is correct
16 Correct 79 ms 11096 KB Output is correct
17 Correct 203 ms 4188 KB Output is correct
18 Correct 13 ms 7768 KB Output is correct

Subtask #2
21.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 1264 KB Output is correct
2 Execution timed out 2047 ms 14420 KB Time limit exceeded
3 Execution timed out 2024 ms 80268 KB Time limit exceeded
4 Execution timed out 2032 ms 27268 KB Time limit exceeded
5 Execution timed out 2005 ms 45200 KB Time limit exceeded
6 Execution timed out 2077 ms 788308 KB Time limit exceeded
7 Correct 386 ms 1340 KB Output is correct
8 Correct 440 ms 1108 KB Output is correct
9 Correct 56 ms 1116 KB Output is correct
10 Correct 139 ms 816 KB Output is correct
11 Correct 107 ms 1104 KB Output is correct
12 Correct 539 ms 924 KB Output is correct
13 Execution timed out 2057 ms 14420 KB Time limit exceeded
14 Correct 1825 ms 9044 KB Output is correct
15 Execution timed out 2070 ms 6528 KB Time limit exceeded
16 Execution timed out 2012 ms 6084 KB Time limit exceeded
17 Execution timed out 2058 ms 31592 KB Time limit exceeded
18 Execution timed out 2029 ms 21076 KB Time limit exceeded
19 Execution timed out 2016 ms 27120 KB Time limit exceeded
20 Execution timed out 2063 ms 18452 KB Time limit exceeded
21 Execution timed out 2067 ms 47444 KB Time limit exceeded
22 Execution timed out 2056 ms 45144 KB Time limit exceeded
23 Execution timed out 2029 ms 50256 KB Time limit exceeded
24 Execution timed out 2067 ms 46268 KB Time limit exceeded
25 Execution timed out 2064 ms 79632 KB Time limit exceeded
26 Correct 117 ms 60436 KB Output is correct
27 Correct 1844 ms 829416 KB Output is correct
28 Execution timed out 2028 ms 788288 KB Time limit exceeded
29 Execution timed out 2087 ms 810472 KB Time limit exceeded
30 Execution timed out 2058 ms 812284 KB Time limit exceeded
31 Execution timed out 2028 ms 187548 KB Time limit exceeded
32 Execution timed out 2031 ms 495720 KB Time limit exceeded