oj.uz

Submission #1095778

# Submission time Handle Problem Language Result Execution time Memory
1095778 2024-10-03T07:18:29 Z ezzzay Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1423 ms 494160 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;
            }
            
        }
        if(y==0 or x==0)continue;
        vis[y][x]=1;
        lvl[y][x]=p;
        char c=a[y][x];
        for(int i=0;i<4;i++){
            if(vis[y+yy[i]][x+xx[i]]==0){
                if(a[y+yy[i]][x+xx[i]]==c){
                    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 26 ms 14672 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 14 ms 12932 KB Output is correct
5 Correct 7 ms 6748 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 2140 KB Output is correct
10 Correct 5 ms 5212 KB Output is correct
11 Correct 4 ms 4668 KB Output is correct
12 Correct 10 ms 7376 KB Output is correct
13 Correct 6 ms 6716 KB Output is correct
14 Correct 6 ms 6748 KB Output is correct
15 Correct 24 ms 13404 KB Output is correct
16 Correct 25 ms 14792 KB Output is correct
17 Correct 19 ms 13916 KB Output is correct
18 Correct 15 ms 13144 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 57300 KB Output is correct
2 Correct 99 ms 39764 KB Output is correct
3 Correct 643 ms 188244 KB Output is correct
4 Correct 194 ms 116436 KB Output is correct
5 Correct 409 ms 172276 KB Output is correct
6 Correct 1305 ms 494084 KB Output is correct
7 Correct 21 ms 59472 KB Output is correct
8 Correct 23 ms 57180 KB Output is correct
9 Correct 4 ms 1628 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 20 ms 56668 KB Output is correct
12 Correct 2 ms 3416 KB Output is correct
13 Correct 92 ms 39760 KB Output is correct
14 Correct 72 ms 26448 KB Output is correct
15 Correct 70 ms 41304 KB Output is correct
16 Correct 45 ms 16464 KB Output is correct
17 Correct 235 ms 79956 KB Output is correct
18 Correct 202 ms 131728 KB Output is correct
19 Correct 187 ms 116432 KB Output is correct
20 Correct 144 ms 60064 KB Output is correct
21 Correct 381 ms 126332 KB Output is correct
22 Correct 420 ms 172368 KB Output is correct
23 Correct 446 ms 130684 KB Output is correct
24 Correct 360 ms 133184 KB Output is correct
25 Correct 877 ms 457600 KB Output is correct
26 Correct 701 ms 152856 KB Output is correct
27 Correct 978 ms 382800 KB Output is correct
28 Correct 1342 ms 494160 KB Output is correct
29 Correct 1423 ms 493652 KB Output is correct
30 Correct 1231 ms 434648 KB Output is correct
31 Correct 1065 ms 306420 KB Output is correct
32 Correct 919 ms 302948 KB Output is correct