oj.uz

Submission #681355

# Submission time Handle Problem Language Result Execution time Memory
681355 2023-01-12T20:21:14 Z MasterTaster Tracks in the Snow (BOI13_tracks) C++14
12.0833 / 100
 1788 ms 1048576 KB 
#include <iostream>
#include <string>
#include <vector>
#include <assert.h>

#define MAXN 4010
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second

using namespace std;

int n, m, a[MAXN][MAXN], cnt, ress;
int x[4], y[4];
bool vis[MAXN][MAXN];
vector<pii> nw1, nw2;

void dfs(int i, int j)
{
    //cout<<"usao "<<i<<" "<<j<<" "<<cnt<<endl;
    vis[i][j]=true;
    for (int k=0; k<4; k++)
    {
        ///(                out of bounds                )    (     visited     )    (         same            )
        if (/*i+x[k]<=0 || i+x[k]>n || j+y[k]<=0 || j+y[k]>m || */vis[i+x[k]][j+y[k]] || a[i+x[k]][j+y[k]]!=a[i][j]) continue;
        dfs(i+x[k], j+y[k]);
    }
}

int main() {
    cin>>n>>m;

    x[0]=-1; x[1]=0; x[2]=1; x[3]=0; ///up right down left
    y[0]=0; y[1]=1; y[2]=0; y[3]=-1; ///up right down left

    for (int i=0; i<=max(n, m); i++) vis[i][0]=vis[0][i]=vis[i][m+1]=vis[n+1][i]=true;
    for (int i=1; i<=n; i++)
    {
        string s; cin>>s;
        for (int j=1; j<=m; j++)
        {
            if (s[j-1]=='.') { a[i][j]=0; cnt++; }
            else if (s[j-1]=='R') a[i][j]=1;
            else a[i][j]=2;
        }
    }
    //for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) cout<<a[i][j]<<" "; cout<<endl; }

    dfs(1, 1);
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (vis[i][j]) { nw2.pb({i, j}); cnt++; }
    ress=1;

    int which=3-a[1][1];
    //cout<<cnt<<endl;
    while (cnt<n*m)
    {
        vector<pii> nww;
        nww.clear();

        for (auto p:nw1)
        {
            for (int i=0; i<4; i++)
            {
                if (!vis[p.xx+x[i]][p.yy+y[i]] && a[p.xx+x[i]][p.yy+y[i]]==which)
                {
                    vis[p.xx+x[i]][p.yy+y[i]]=true;
                    nww.pb({p.xx+x[i], p.yy+y[i]});
                }
            }
        }
        for (auto p:nw2)
        {
            for (int i=0; i<4; i++)
            {
                if (!vis[p.xx+x[i]][p.yy+y[i]] && a[p.xx+x[i]][p.yy+y[i]]==which)
                {
                    vis[p.xx+x[i]][p.yy+y[i]]=true;
                    nww.pb({p.xx+x[i], p.yy+y[i]});
                }
            }
        }
        if (nww.size()==0) assert(0);


        nw1=nw2;
        nw2.clear();
        for (int i=0; i<nww.size(); i++) { nw2.pb(nww[i]); cnt++; }

        ress++;
        which=3-which;
    }
    cout<<ress;
}

Compilation message

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

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 5588 KB Output isn't correct
2 Correct 1 ms 468 KB Output is correct
3 Runtime error 3 ms 1236 KB Execution killed with signal 6
4 Runtime error 24 ms 14132 KB Execution killed with signal 6
5 Runtime error 11 ms 5884 KB Execution killed with signal 6
6 Correct 0 ms 436 KB Output is correct
7 Runtime error 3 ms 1236 KB Execution killed with signal 6
8 Incorrect 1 ms 956 KB Output isn't correct
9 Runtime error 4 ms 2132 KB Execution killed with signal 6
10 Runtime error 12 ms 5184 KB Execution killed with signal 6
11 Runtime error 9 ms 6036 KB Execution killed with signal 6
12 Runtime error 14 ms 6152 KB Execution killed with signal 6
13 Runtime error 13 ms 5972 KB Execution killed with signal 6
14 Runtime error 10 ms 5972 KB Execution killed with signal 6
15 Runtime error 30 ms 11000 KB Execution killed with signal 6
16 Incorrect 22 ms 5588 KB Output isn't correct
17 Runtime error 27 ms 10592 KB Execution killed with signal 6
18 Runtime error 25 ms 14056 KB Execution killed with signal 6

Subtask #2
8.75 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 63012 KB Execution killed with signal 6
2 Runtime error 123 ms 35004 KB Execution killed with signal 6
3 Runtime error 451 ms 176500 KB Execution killed with signal 6
4 Runtime error 195 ms 65792 KB Execution killed with signal 6
5 Correct 387 ms 68404 KB Output is correct
6 Incorrect 1622 ms 218392 KB Output isn't correct
7 Runtime error 70 ms 66060 KB Execution killed with signal 6
8 Runtime error 66 ms 63052 KB Execution killed with signal 6
9 Runtime error 24 ms 32844 KB Execution killed with signal 6
10 Runtime error 22 ms 33256 KB Execution killed with signal 6
11 Runtime error 69 ms 64764 KB Execution killed with signal 6
12 Correct 2 ms 1620 KB Output is correct
13 Runtime error 122 ms 35040 KB Execution killed with signal 6
14 Runtime error 72 ms 24096 KB Execution killed with signal 6
15 Runtime error 48 ms 25828 KB Execution killed with signal 6
16 Runtime error 58 ms 22596 KB Execution killed with signal 6
17 Runtime error 292 ms 69820 KB Execution killed with signal 6
18 Runtime error 146 ms 68972 KB Execution killed with signal 6
19 Runtime error 194 ms 65700 KB Execution killed with signal 6
20 Runtime error 127 ms 61656 KB Execution killed with signal 6
21 Runtime error 280 ms 133928 KB Execution killed with signal 6
22 Correct 393 ms 68492 KB Output is correct
23 Runtime error 540 ms 113632 KB Execution killed with signal 6
24 Runtime error 277 ms 132616 KB Execution killed with signal 6
25 Runtime error 455 ms 176568 KB Execution killed with signal 6
26 Correct 1351 ms 979460 KB Output is correct
27 Runtime error 1788 ms 1048576 KB Execution killed with signal 6
28 Incorrect 1618 ms 218256 KB Output isn't correct
29 Runtime error 1729 ms 457340 KB Execution killed with signal 6
30 Runtime error 1553 ms 470404 KB Execution killed with signal 6
31 Runtime error 1162 ms 140492 KB Execution killed with signal 6
32 Runtime error 1062 ms 176732 KB Execution killed with signal 6