oj.uz

Submission #1095772

# Submission time Handle Problem Language Result Execution time Memory
1095772 2024-10-03T07:06:33 Z ezzzay Tracks in the Snow (BOI13_tracks) C++14
43.3333 / 100
 2000 ms 1048580 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();
        }
        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 1370 ms 1048576 KB Execution killed with signal 9
2 Correct 0 ms 604 KB Output is correct
3 Correct 14 ms 4440 KB Output is correct
4 Runtime error 1569 ms 1048576 KB Execution killed with signal 9
5 Execution timed out 2100 ms 845276 KB Time limit exceeded
6 Correct 0 ms 604 KB Output is correct
7 Correct 9 ms 4556 KB Output is correct
8 Runtime error 1544 ms 1048576 KB Execution killed with signal 9
9 Correct 2 ms 2136 KB Output is correct
10 Runtime error 1636 ms 1048576 KB Execution killed with signal 9
11 Runtime error 1676 ms 1048576 KB Execution killed with signal 9
12 Runtime error 1456 ms 1048580 KB Execution killed with signal 9
13 Execution timed out 2040 ms 812416 KB Time limit exceeded
14 Execution timed out 2070 ms 738172 KB Time limit exceeded
15 Runtime error 1495 ms 1048576 KB Execution killed with signal 9
16 Runtime error 1466 ms 1048576 KB Execution killed with signal 9
17 Runtime error 1626 ms 1048576 KB Execution killed with signal 9
18 Runtime error 1637 ms 1048576 KB Execution killed with signal 9

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 57180 KB Output is correct
2 Runtime error 1729 ms 1048576 KB Execution killed with signal 9
3 Correct 640 ms 185396 KB Output is correct
4 Execution timed out 2073 ms 600860 KB Time limit exceeded
5 Correct 417 ms 163412 KB Output is correct
6 Runtime error 1858 ms 1048576 KB Execution killed with signal 9
7 Correct 32 ms 59476 KB Output is correct
8 Correct 22 ms 57120 KB Output is correct
9 Correct 365 ms 155564 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 22 ms 56580 KB Output is correct
12 Correct 2 ms 3416 KB Output is correct
13 Runtime error 1713 ms 1048576 KB Execution killed with signal 9
14 Execution timed out 2093 ms 812352 KB Time limit exceeded
15 Correct 57 ms 41088 KB Output is correct
16 Execution timed out 2129 ms 995372 KB Time limit exceeded
17 Execution timed out 2047 ms 708712 KB Time limit exceeded
18 Correct 219 ms 130132 KB Output is correct
19 Execution timed out 2094 ms 531096 KB Time limit exceeded
20 Correct 170 ms 58704 KB Output is correct
21 Correct 460 ms 124436 KB Output is correct
22 Correct 466 ms 168392 KB Output is correct
23 Execution timed out 2054 ms 668464 KB Time limit exceeded
24 Correct 354 ms 129048 KB Output is correct
25 Correct 899 ms 450128 KB Output is correct
26 Runtime error 1955 ms 1048576 KB Execution killed with signal 9
27 Execution timed out 2005 ms 1048576 KB Time limit exceeded
28 Runtime error 1830 ms 1048576 KB Execution killed with signal 9
29 Execution timed out 2104 ms 1016044 KB Time limit exceeded
30 Execution timed out 2069 ms 1048576 KB Time limit exceeded
31 Runtime error 1727 ms 1048576 KB Execution killed with signal 9
32 Execution timed out 2110 ms 852940 KB Time limit exceeded