oj.uz

답안 #988060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
988060 2024-05-24T02:32:26 Z sarthakgangwal Tracks in the Snow (BOI13_tracks) C++17
84.6875 / 100
 2000 ms 207524 KB 
//This code is written by sarthakgangwal
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define tc int t;cin>>t;while(t--)
#define el "/n"
#define sp ' '
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define vvpll vector<vector<pair<long long int, long long int>>>
#define vpll vector<pair<long long int,long long int>>
#define vb vector<bool>
#define pb push_back
#define pll pair<long long int,long long int>
#define ff first
#define ss second
#define I(x) ll x;cin>>x
#define CC(x) cout << (x) << endl
#define mod 1000000007
#define PI 3.14159265
long long INF = 2e18;
#define vll_in(v,n) for(ll i=0;i<=n-1;i++){ ll x;cin>>x; v.push_back(x);}
#define vvll_in(mat,r,c) for(ll i=0;i<=r-1;i++){ vector<ll> v;for(ll j=0;j<=c-1;j++){ll x;cin>>x;v.push_back(x);};mat.push_back(v);}
void print(bool k){cout << (k ? "YES" : "NO") <<"\n";}
void print(vll k,string sep = " ",string endline = "\n") {for (ll &i : k) cout << i << sep; cout << endline;}
#define all(x) (x).begin(), (x).end()

/*-------------------------------------Imp Concepts---------------------------------------------->
48-57 -> 0-9
65-90 -> A-Z
97-122 -> a-z
(a +-* b) mod M = ((a mod M) +-* (b mod M)) mod M.

use ordered set using oset<ll> , 2 extra functions
.order_of_key(k) gives number of items strictly smaller than k
.find_by_order(k) gives iterator to kth element in set 0 indexing
rest all functionalities are same as stl set like lowerbound upperbound erase find etc

use ordered multiset using oset<pll>
search upper_bound({val,-1})
insert insert({val,index}) index used so same val can be inserted uniquely
delete .erase( .upper_bound({val,-1}))
-----------------------------CODE BEGIN :)-----------------------------------------*/

//https://oj.uz/problem/view/BOI13_tracks
int main(){
    fast
    {
        I(h);I(w);
        // ll mat[h+2][w+2]={0};
        vvll mat(h+2,vll(w+2,0));

        for(ll i=1;i<=h;i++){
            for(ll j=1;j<=w;j++){
                char x;cin>>x;
                if(x=='F'){mat[i][j]=1;}
                if(x=='R'){mat[i][j]=2;}   
            }
        }

        bool vis[h+2][w+2]={0};
        ll ans=1;

        ll movx[4]={1,0,-1,0}, movy[4]={0,1,0,-1};
        priority_queue<pair<ll,pll>, vector<pair<ll,pll>>, greater<pair<ll,pll>>> pq;
        pq.push({1,{1,1}}); vis[1][1]=1;
        while(!pq.empty()){
            pair<ll,pll> T = pq.top(); pq.pop();
            ll x=T.ss.ff, y=T.ss.ss, d=T.ff;
            // cout<<x<<sp<<y<<sp<<d<<endl;
            for(ll i=0;i<4;i++){
                ll xx=x+movx[i], yy=y+movy[i];

                if(mat[xx][yy]==0){continue;}
                else if(vis[xx][yy]==0 && mat[xx][yy]==mat[x][y]){
                    vis[xx][yy]=1; pq.push({d,{xx,yy}});
                }
                else if(vis[xx][yy]==0 && mat[xx][yy]!=mat[x][y]){
                    vis[xx][yy]=1; pq.push({d+1,{xx,yy}});
                    ans=max(ans,d+1);
                }
            }
        }
        CC(ans);

    }
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 3096 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 25 ms 2392 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 548 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 5 ms 1116 KB Output is correct
11 Correct 7 ms 1116 KB Output is correct
12 Correct 14 ms 1368 KB Output is correct
13 Correct 5 ms 1112 KB Output is correct
14 Correct 5 ms 1116 KB Output is correct
15 Correct 31 ms 3108 KB Output is correct
16 Correct 41 ms 3100 KB Output is correct
17 Correct 21 ms 2904 KB Output is correct
18 Correct 25 ms 2388 KB Output is correct

Subtask #2
54.6875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 120 ms 15968 KB Output is correct
3 Correct 460 ms 157340 KB Output is correct
4 Correct 165 ms 37328 KB Output is correct
5 Correct 212 ms 88516 KB Output is correct
6 Execution timed out 2020 ms 207524 KB Time limit exceeded
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 5 ms 1068 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 116 ms 15968 KB Output is correct
14 Correct 65 ms 9308 KB Output is correct
15 Correct 27 ms 10184 KB Output is correct
16 Correct 58 ms 6900 KB Output is correct
17 Correct 314 ms 40272 KB Output is correct
18 Correct 168 ms 39764 KB Output is correct
19 Correct 159 ms 37200 KB Output is correct
20 Correct 108 ms 34032 KB Output is correct
21 Correct 273 ms 91780 KB Output is correct
22 Correct 210 ms 88660 KB Output is correct
23 Correct 639 ms 76688 KB Output is correct
24 Correct 211 ms 89628 KB Output is correct
25 Correct 844 ms 157464 KB Output is correct
26 Correct 1138 ms 120904 KB Output is correct
27 Execution timed out 2056 ms 165152 KB Time limit exceeded
28 Execution timed out 2050 ms 206728 KB Time limit exceeded
29 Execution timed out 2039 ms 182712 KB Time limit exceeded
30 Execution timed out 2025 ms 179396 KB Time limit exceeded
31 Execution timed out 2025 ms 102624 KB Time limit exceeded
32 Execution timed out 2071 ms 160444 KB Time limit exceeded