oj.uz

Submission #1095773

# Submission time Handle Problem Language Result Execution time Memory
1095773 2024-10-03T07:06:57 Z ezzzay Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1439 ms 493908 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{
            while(!hq.empty()){
                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;
                    break;
                }
                
            }
            if(vis[y][x])continue;
            
        }
        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 24 ms 14696 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 21 ms 12836 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 1476 KB Output is correct
9 Correct 1 ms 2140 KB Output is correct
10 Correct 8 ms 5208 KB Output is correct
11 Correct 5 ms 4696 KB Output is correct
12 Correct 9 ms 7332 KB Output is correct
13 Correct 6 ms 6748 KB Output is correct
14 Correct 6 ms 6748 KB Output is correct
15 Correct 20 ms 13400 KB Output is correct
16 Correct 35 ms 14672 KB Output is correct
17 Correct 24 ms 13900 KB Output is correct
18 Correct 15 ms 13072 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 57176 KB Output is correct
2 Correct 95 ms 38260 KB Output is correct
3 Correct 629 ms 174400 KB Output is correct
4 Correct 187 ms 114260 KB Output is correct
5 Correct 468 ms 171916 KB Output is correct
6 Correct 1326 ms 493908 KB Output is correct
7 Correct 23 ms 59740 KB Output is correct
8 Correct 21 ms 57180 KB Output is correct
9 Correct 3 ms 1628 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 21 ms 56504 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 88 ms 39684 KB Output is correct
14 Correct 56 ms 26452 KB Output is correct
15 Correct 53 ms 41324 KB Output is correct
16 Correct 39 ms 16468 KB Output is correct
17 Correct 261 ms 79952 KB Output is correct
18 Correct 219 ms 131764 KB Output is correct
19 Correct 192 ms 116308 KB Output is correct
20 Correct 156 ms 59984 KB Output is correct
21 Correct 433 ms 125780 KB Output is correct
22 Correct 421 ms 171696 KB Output is correct
23 Correct 468 ms 130020 KB Output is correct
24 Correct 378 ms 132600 KB Output is correct
25 Correct 902 ms 456172 KB Output is correct
26 Correct 786 ms 152744 KB Output is correct
27 Correct 1088 ms 382556 KB Output is correct
28 Correct 1439 ms 493904 KB Output is correct
29 Correct 1367 ms 493008 KB Output is correct
30 Correct 1190 ms 434160 KB Output is correct
31 Correct 1049 ms 306028 KB Output is correct
32 Correct 1036 ms 302312 KB Output is correct