oj.uz

Submission #1095771

# Submission time Handle Problem Language Result Execution time Memory
1095771 2024-10-03T07:04:37 Z ezzzay Tracks in the Snow (BOI13_tracks) C++14
43.3333 / 100
 2000 ms 1048576 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;
    hq.push({n,m});
    int p=0;
    while(!(q.empty() and hq.empty())){
        int y,x;
        if(!q.empty()){
            y=q.front().ff,x=q.front().ss;
            q.pop();
        }
        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
8.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1341 ms 1048576 KB Execution killed with signal 9
2 Correct 0 ms 600 KB Output is correct
3 Correct 9 ms 4444 KB Output is correct
4 Runtime error 1600 ms 1048576 KB Execution killed with signal 9
5 Execution timed out 2088 ms 722100 KB Time limit exceeded
6 Correct 1 ms 604 KB Output is correct
7 Correct 10 ms 4484 KB Output is correct
8 Runtime error 1567 ms 1048576 KB Execution killed with signal 9
9 Correct 2 ms 2140 KB Output is correct
10 Runtime error 1600 ms 1048576 KB Execution killed with signal 9
11 Runtime error 1624 ms 1048576 KB Execution killed with signal 9
12 Runtime error 1450 ms 1048576 KB Execution killed with signal 9
13 Execution timed out 2062 ms 784824 KB Time limit exceeded
14 Execution timed out 2100 ms 845236 KB Time limit exceeded
15 Runtime error 1448 ms 1048576 KB Execution killed with signal 9
16 Runtime error 1418 ms 1048576 KB Execution killed with signal 9
17 Runtime error 1642 ms 1048576 KB Execution killed with signal 9
18 Runtime error 1600 ms 1048576 KB Execution killed with signal 9

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 57176 KB Output is correct
2 Runtime error 1845 ms 1048576 KB Execution killed with signal 9
3 Correct 703 ms 185092 KB Output is correct
4 Execution timed out 2071 ms 524092 KB Time limit exceeded
5 Correct 416 ms 170324 KB Output is correct
6 Execution timed out 2059 ms 1048576 KB Time limit exceeded
7 Correct 25 ms 59736 KB Output is correct
8 Correct 23 ms 57176 KB Output is correct
9 Correct 338 ms 155460 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 23 ms 56660 KB Output is correct
12 Correct 3 ms 3420 KB Output is correct
13 Runtime error 1849 ms 1048576 KB Execution killed with signal 9
14 Execution timed out 2125 ms 792640 KB Time limit exceeded
15 Correct 61 ms 41304 KB Output is correct
16 Execution timed out 2076 ms 995180 KB Time limit exceeded
17 Execution timed out 2075 ms 760620 KB Time limit exceeded
18 Correct 228 ms 131004 KB Output is correct
19 Execution timed out 2061 ms 523992 KB Time limit exceeded
20 Correct 160 ms 59732 KB Output is correct
21 Correct 417 ms 126420 KB Output is correct
22 Correct 435 ms 170320 KB Output is correct
23 Execution timed out 2083 ms 589620 KB Time limit exceeded
24 Correct 396 ms 131224 KB Output is correct
25 Correct 854 ms 454228 KB Output is correct
26 Runtime error 1934 ms 1048576 KB Execution killed with signal 9
27 Execution timed out 2092 ms 1048576 KB Time limit exceeded
28 Runtime error 1897 ms 1048576 KB Execution killed with signal 9
29 Execution timed out 2082 ms 929864 KB Time limit exceeded
30 Execution timed out 2057 ms 1048412 KB Time limit exceeded
31 Runtime error 1718 ms 1048576 KB Execution killed with signal 9
32 Execution timed out 2059 ms 716556 KB Time limit exceeded