oj.uz

Submission #1095780

# Submission time Handle Problem Language Result Execution time Memory
1095780 2024-10-03T07:20:22 Z ezzzay Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1406 ms 478608 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ff first
#define ss second
#define pb push_back
const int N=4444;
char a[N][N];
bool vis[N][N];
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
pair<int,int>par[N][N];
int lvl[N][N];
bool lvlvis[N*N];
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    queue<pair<int,int>>q,hq;
    q.push({n,m});
    int p=1;
    while(!(q.empty() and hq.empty())){
        int y,x;
        if(!q.empty()){
            y=q.front().ff,x=q.front().ss;
            q.pop();
            if(vis[y][x])continue;
        }
        else{
            y=hq.front().ff,x=hq.front().ss;
            hq.pop();
            if(vis[y][x]==0){
                int py=par[y][x].ff,px=par[y][x].ss;
                if(lvlvis[lvl[py][px]]==0)p++;
                lvlvis[lvl[py][px]]=1;
            }
        }
        vis[y][x]=1;
        lvl[y][x]=p;
        for(int i=0;i<4;i++){
            if(vis[y+yy[i]][x+xx[i]]==0){
                if(a[y+yy[i]][x+xx[i]]==a[y][x]){
                    q.push({y+yy[i],x+xx[i]});
                }
                else if(a[y+yy[i]][x+xx[i]]=='F' or a[y+yy[i]][x+xx[i]]=='R'){
                    par[y+yy[i]][x+xx[i]]={y,x};
                    hq.push({y+yy[i],x+xx[i]});
                }
            }
        }
    }
    cout<<p;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14420 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 14 ms 12860 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 1112 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1948 KB Output is correct
10 Correct 5 ms 5212 KB Output is correct
11 Correct 4 ms 4700 KB Output is correct
12 Correct 14 ms 7260 KB Output is correct
13 Correct 6 ms 6744 KB Output is correct
14 Correct 6 ms 6748 KB Output is correct
15 Correct 23 ms 13148 KB Output is correct
16 Correct 25 ms 14420 KB Output is correct
17 Correct 19 ms 13652 KB Output is correct
18 Correct 15 ms 12892 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 57176 KB Output is correct
2 Correct 94 ms 38192 KB Output is correct
3 Correct 658 ms 172500 KB Output is correct
4 Correct 188 ms 112688 KB Output is correct
5 Correct 394 ms 163408 KB Output is correct
6 Correct 1406 ms 478596 KB Output is correct
7 Correct 23 ms 59484 KB Output is correct
8 Correct 22 ms 57176 KB Output is correct
9 Correct 4 ms 1368 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 28 ms 56544 KB Output is correct
12 Correct 3 ms 3668 KB Output is correct
13 Correct 101 ms 38228 KB Output is correct
14 Correct 58 ms 25684 KB Output is correct
15 Correct 59 ms 40452 KB Output is correct
16 Correct 51 ms 15672 KB Output is correct
17 Correct 251 ms 76104 KB Output is correct
18 Correct 209 ms 127824 KB Output is correct
19 Correct 181 ms 112720 KB Output is correct
20 Correct 150 ms 56500 KB Output is correct
21 Correct 383 ms 117076 KB Output is correct
22 Correct 383 ms 163608 KB Output is correct
23 Correct 465 ms 122960 KB Output is correct
24 Correct 348 ms 124240 KB Output is correct
25 Correct 812 ms 441940 KB Output is correct
26 Correct 684 ms 140896 KB Output is correct
27 Correct 1071 ms 367152 KB Output is correct
28 Correct 1386 ms 478608 KB Output is correct
29 Correct 1352 ms 478040 KB Output is correct
30 Correct 1208 ms 419412 KB Output is correct
31 Correct 1000 ms 296244 KB Output is correct
32 Correct 900 ms 287312 KB Output is correct