oj.uz

답안 #1091832

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1091832 2024-09-22T10:15:37 Z Jakub_Wozniak Tracks in the Snow (BOI13_tracks) C++14
93.4375 / 100
 2000 ms 76716 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4009;
typedef long long ll;
int N , M;
string s[maxn];
string SA;
int a , b , c;
vector <pair<int,int>> R;
bool vis[maxn][maxn];
int MAXI = 0;

void pr()
{
    R.push_back({-1,0});
    R.push_back({1,0});
    R.push_back({0,1});
    R.push_back({0,-1});
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for(int i = 0 ; i <= M+1 ; i++)SA.push_back( '.');
    s[0] = SA;
    s[N+1] = SA;


    pr();
    for(int i = 1 ; i <= N  ;i++)
    {
        cin >> SA;
        s[i] = '.';
        s[i] += SA;
        s[i].push_back('.');
    }

    priority_queue <pair<int,int>> q;
    pair<int,int> DS;
    q.push({-1,1*maxn+1});
    int i , j;
    vis[1][1] = 1;

    while(!q.empty())
    {
        DS = q.top();
        c = -DS.first; 
        i = DS.second/maxn;
        j = DS.second-i*maxn;
        q.pop();
        
        MAXI = max(MAXI , c);

        for(int k = 0 ; k < R.size() ; k++)
        {
            a = i+R[k].first;
            b = j+R[k].second;
            if(s[a][b] == '.' || vis[a][b])continue;
            vis[a][b] = 1;
            if(s[a][b] == s[i][j]){ q.push({-c,a*maxn+b});}
            else {q.push({-(c+1),a*maxn+b});}
        }
    }

    cout << MAXI << '\n';


    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int k = 0 ; k < R.size() ; k++)
      |                         ~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3164 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 16 ms 3164 KB Output is correct
5 Correct 3 ms 1732 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 3 ms 1628 KB Output is correct
11 Correct 5 ms 1372 KB Output is correct
12 Correct 9 ms 2056 KB Output is correct
13 Correct 3 ms 1884 KB Output is correct
14 Correct 3 ms 1884 KB Output is correct
15 Correct 20 ms 3356 KB Output is correct
16 Correct 27 ms 3160 KB Output is correct
17 Correct 13 ms 3164 KB Output is correct
18 Correct 16 ms 3256 KB Output is correct

Subtask #2
63.4375 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 15452 KB Output is correct
2 Correct 73 ms 10128 KB Output is correct
3 Correct 234 ms 60152 KB Output is correct
4 Correct 81 ms 18448 KB Output is correct
5 Correct 134 ms 36972 KB Output is correct
6 Execution timed out 2029 ms 76512 KB Time limit exceeded
7 Correct 6 ms 16220 KB Output is correct
8 Correct 6 ms 15428 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 6 ms 15964 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 71 ms 10132 KB Output is correct
14 Correct 41 ms 6744 KB Output is correct
15 Correct 12 ms 7260 KB Output is correct
16 Correct 38 ms 4088 KB Output is correct
17 Correct 213 ms 19636 KB Output is correct
18 Correct 49 ms 19292 KB Output is correct
19 Correct 78 ms 18524 KB Output is correct
20 Correct 56 ms 17120 KB Output is correct
21 Correct 137 ms 38224 KB Output is correct
22 Correct 127 ms 36940 KB Output is correct
23 Correct 377 ms 31824 KB Output is correct
24 Correct 106 ms 37968 KB Output is correct
25 Correct 211 ms 59996 KB Output is correct
26 Correct 935 ms 47956 KB Output is correct
27 Correct 1635 ms 62144 KB Output is correct
28 Execution timed out 2017 ms 76716 KB Time limit exceeded
29 Execution timed out 2084 ms 68532 KB Time limit exceeded
30 Correct 1969 ms 67088 KB Output is correct
31 Correct 1290 ms 42200 KB Output is correct
32 Correct 1194 ms 62976 KB Output is correct