oj.uz

Submission #1095781

# Submission time Handle Problem Language Result Execution time Memory
1095781 2024-10-03T07:20:54 Z ezzzay Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1423 ms 478548 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<1 or y>n or x<1 or x>m)continue;
        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 26 ms 14424 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 12892 KB Output is correct
5 Correct 6 ms 6748 KB Output is correct
6 Correct 1 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 4700 KB Output is correct
12 Correct 14 ms 7336 KB Output is correct
13 Correct 5 ms 6748 KB Output is correct
14 Correct 9 ms 6748 KB Output is correct
15 Correct 23 ms 13148 KB Output is correct
16 Correct 26 ms 14420 KB Output is correct
17 Correct 18 ms 13656 KB Output is correct
18 Correct 13 ms 12892 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 57180 KB Output is correct
2 Correct 93 ms 38212 KB Output is correct
3 Correct 633 ms 172624 KB Output is correct
4 Correct 180 ms 112720 KB Output is correct
5 Correct 412 ms 163408 KB Output is correct
6 Correct 1414 ms 478528 KB Output is correct
7 Correct 24 ms 59472 KB Output is correct
8 Correct 25 ms 57176 KB Output is correct
9 Correct 4 ms 1372 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 23 ms 56644 KB Output is correct
12 Correct 3 ms 3420 KB Output is correct
13 Correct 127 ms 38072 KB Output is correct
14 Correct 63 ms 25680 KB Output is correct
15 Correct 58 ms 40276 KB Output is correct
16 Correct 48 ms 15700 KB Output is correct
17 Correct 249 ms 76232 KB Output is correct
18 Correct 223 ms 127824 KB Output is correct
19 Correct 194 ms 112724 KB Output is correct
20 Correct 144 ms 56528 KB Output is correct
21 Correct 369 ms 117120 KB Output is correct
22 Correct 384 ms 163408 KB Output is correct
23 Correct 443 ms 122960 KB Output is correct
24 Correct 352 ms 124244 KB Output is correct
25 Correct 829 ms 441940 KB Output is correct
26 Correct 742 ms 140764 KB Output is correct
27 Correct 1056 ms 367112 KB Output is correct
28 Correct 1423 ms 478548 KB Output is correct
29 Correct 1375 ms 478040 KB Output is correct
30 Correct 1255 ms 419504 KB Output is correct
31 Correct 1110 ms 296244 KB Output is correct
32 Correct 907 ms 287312 KB Output is correct