oj.uz

Submission #1102704

# Submission time Handle Problem Language Result Execution time Memory
1102704 2024-10-18T16:47:45 Z salmon Mecho (IOI09_mecho) C++14
4 / 100
 966 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

int N;
int S;
vector<pair<int,int>> trans = {{1,0}, {-1,0},{0,1},{0,-1}};
char clst[810][810];
int s1,s2;
int f1,f2;
queue<pair<int,int>> q[2];
queue<pair<int,int>> m[2];
bool visited[810][810];
bool vt[810][810];
int d[810][810];
int cq,cm;

bool check(int i, int j){
    if(i < 0) return false;
    if(i >= N) return false;
    if(j < 0) return false;
    if(j >= N) return false;
    return true;
}

void spreadhoney(int it){
    while(!q[it].empty()){
        pair<int,int> ii = q[it].front();
        q[it].pop();

        int i = ii.first;
        int j = ii.second;

        visited[i][j] = true;
        vt[i][j] = true;

        for(pair<int,int> ii : trans){
            int ni = ii.first + i;
            int nj = ii.second + j;

            if(!check(ni,nj)) continue;
            if(visited[ni][nj]) continue;
            q[1 - it].push({ni,nj});
        }
    }
}

int main(){
    scanf(" %d",&N);
    scanf(" %d",&S);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            scanf(" %c",&clst[i][j]);
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            visited[i][j] = false;
            vt[i][j] = false;
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(clst[i][j] == 'T'){
                visited[i][j] = true;
                vt[i][j] = true;
            }
            else if(clst[i][j] == 'H'){
                q[1].push({i,j});
            }
            else if(clst[i][j] == 'M'){
                s1 = i;
                s2 = j;
            }
            else if(clst[i][j] == 'D'){
                f1 = i;
                f2 = j;
                visited[i][j] = true;
            }
        }
    }

    cq = 0;
    cm = 0;

    spreadhoney(1);

    vt[s1][s2] = true;

    for(pair<int,int> ii : trans){
        int ni = s1 + ii.first;
        int nj = s2 + ii.second;

        if(!check(ni,nj)) continue;
        m[0].push({ni,nj});
    }

    bool flag;

    while(true){
        int it = cm % 2;

        bool done = false;

        for(int i = 0; i < S; i++, cm++){
            it = cm % 2;

            while(!m[it].empty()){
                pair<int,int> ii = m[it].front();
                m[it].pop();

                int i = ii.first;
                int j = ii.second;

                if(i == f1 && j == f2){
                    done = true;
                    flag = true;
                    break;
                }
                if(vt[i][j]) continue;
                vt[i][j] = true;

                for(pair<int,int> ii : trans){
                    int ni = i + ii.first;
                    int nj = j + ii.second;

                    if(!check(ni,nj)) continue;
                    m[1 - it].push({ni,nj});
                }
            }

            if(done) break;

            if(m[1 - it].empty()){
                done = true;
                flag = false;
                break;
            }
        }

        if(done) break;

        it = cq % 2;
        spreadhoney(it);
        cq++;
    }

    if(!flag){
        printf("-1");
        return 0;
    }

    int s = 0;
    int e = 800*800;
    int m1;

    while(s != e){
        m1 = (s + e + 1)/2;

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                visited[i][j] = false;
                vt[i][j] = false;
            }
        }

        while(!m[0].empty()) m[0].pop();
        while(!m[1].empty()) m[1].pop();
        while(!q[0].empty()) q[0].pop();
        while(!q[1].empty()) q[1].pop();

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(clst[i][j] == 'T'){
                    visited[i][j] = true;
                    vt[i][j] = true;
                }
                else if(clst[i][j] == 'H'){
                    q[1].push({i,j});
                }
                else if(clst[i][j] == 'D'){
                    visited[i][j] = true;
                }
            }
        }

        cq = 0;
        cm = 0;

        spreadhoney(1);

        vt[s1][s2] = true;

        for(pair<int,int> ii : trans){
            int ni = s1 + ii.first;
            int nj = s2 + ii.second;

            if(!check(ni,nj)) continue;
            m[0].push({ni,nj});
        }

        for(int i = 0; i < m1; i++, cq++){
            int it = cq % 2;

            spreadhoney(it);
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                printf("%d ",visited[i][j]);
            }
            printf("\n");
        }
        printf("\n");

        bool flag;

        while(true){
            int it = cm % 2;

            bool done = false;

            for(int i = 0; i < S; i++, cm++){
                it = cm % 2;

                while(!m[it].empty()){
                    pair<int,int> ii = m[it].front();
                    m[it].pop();

                    int i = ii.first;
                    int j = ii.second;
                    //printf("%d %d\n",i,j);

                    if(i == f1 && j == f2){
                        done = true;
                        flag = true;
                        break;
                    }
                    if(vt[i][j]) continue;
                    vt[i][j] = true;

                    for(pair<int,int> ii : trans){
                        int ni = i + ii.first;
                        int nj = j + ii.second;

                        if(!check(ni,nj)) continue;
                        m[1 - it].push({ni,nj});
                    }
                }
                //printf("\n");

                if(done) break;

                if(m[1 - it].empty()){
                    done = true;
                    flag = false;
                    break;
                }
            }

            if(done) break;

            it = cq % 2;
            spreadhoney(it);
            cq++;
        }

        if(flag){
            s = m1;
        }
        else{
            e = m1 - 1;
        }
    }

    printf("%d",s);
}
/*
7 3
TTTTTTT
TGGGGGT
TGGGGGG
MGGGGGD
TGGTTTT
TGGGGGT
TTTTTHT
*/

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
mecho.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf(" %d",&S);
      |     ~~~~~^~~~~~~~~~
mecho.cpp:53:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |             scanf(" %c",&clst[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2384 KB Output isn't correct
2 Incorrect 3 ms 2384 KB Output isn't correct
3 Incorrect 3 ms 2384 KB Output isn't correct
4 Incorrect 3 ms 2552 KB Output isn't correct
5 Incorrect 3 ms 2384 KB Output isn't correct
6 Incorrect 4 ms 2612 KB Output isn't correct
7 Runtime error 230 ms 65536 KB Execution killed with signal 9
8 Incorrect 5 ms 2384 KB Output isn't correct
9 Incorrect 4 ms 2384 KB Output isn't correct
10 Incorrect 6 ms 2548 KB Output isn't correct
11 Incorrect 4 ms 2384 KB Output isn't correct
12 Incorrect 46 ms 2644 KB Output isn't correct
13 Incorrect 121 ms 2896 KB Output isn't correct
14 Correct 3 ms 2640 KB Output is correct
15 Incorrect 3 ms 2384 KB Output isn't correct
16 Incorrect 4 ms 2384 KB Output isn't correct
17 Incorrect 4 ms 2384 KB Output isn't correct
18 Incorrect 4 ms 2384 KB Output isn't correct
19 Incorrect 4 ms 2504 KB Output isn't correct
20 Incorrect 4 ms 2384 KB Output isn't correct
21 Incorrect 5 ms 2384 KB Output isn't correct
22 Incorrect 5 ms 2384 KB Output isn't correct
23 Incorrect 6 ms 2552 KB Output isn't correct
24 Incorrect 6 ms 2384 KB Output isn't correct
25 Incorrect 7 ms 2808 KB Output isn't correct
26 Incorrect 7 ms 2808 KB Output isn't correct
27 Incorrect 8 ms 2640 KB Output isn't correct
28 Incorrect 9 ms 2504 KB Output isn't correct
29 Incorrect 9 ms 2640 KB Output isn't correct
30 Incorrect 9 ms 2640 KB Output isn't correct
31 Incorrect 9 ms 2508 KB Output isn't correct
32 Incorrect 10 ms 2640 KB Output isn't correct
33 Incorrect 158 ms 7424 KB Output isn't correct
34 Incorrect 146 ms 7240 KB Output isn't correct
35 Runtime error 221 ms 65536 KB Execution killed with signal 9
36 Incorrect 184 ms 8520 KB Output isn't correct
37 Incorrect 190 ms 8776 KB Output isn't correct
38 Runtime error 208 ms 65536 KB Execution killed with signal 9
39 Incorrect 247 ms 10176 KB Output isn't correct
40 Incorrect 234 ms 10056 KB Output isn't correct
41 Runtime error 205 ms 65536 KB Execution killed with signal 9
42 Incorrect 286 ms 12552 KB Output isn't correct
43 Incorrect 285 ms 11848 KB Output isn't correct
44 Runtime error 188 ms 65536 KB Execution killed with signal 9
45 Incorrect 338 ms 13876 KB Output isn't correct
46 Incorrect 318 ms 13900 KB Output isn't correct
47 Runtime error 192 ms 65536 KB Execution killed with signal 9
48 Incorrect 408 ms 16200 KB Output isn't correct
49 Incorrect 430 ms 16968 KB Output isn't correct
50 Runtime error 221 ms 65536 KB Execution killed with signal 9
51 Incorrect 483 ms 18712 KB Output isn't correct
52 Incorrect 476 ms 18740 KB Output isn't correct
53 Runtime error 229 ms 65536 KB Execution killed with signal 9
54 Incorrect 575 ms 21300 KB Output isn't correct
55 Incorrect 560 ms 21148 KB Output isn't correct
56 Runtime error 226 ms 65536 KB Execution killed with signal 9
57 Incorrect 733 ms 23984 KB Output isn't correct
58 Incorrect 625 ms 24136 KB Output isn't correct
59 Runtime error 224 ms 65536 KB Execution killed with signal 9
60 Incorrect 816 ms 28368 KB Output isn't correct
61 Incorrect 762 ms 28232 KB Output isn't correct
62 Runtime error 207 ms 65536 KB Execution killed with signal 9
63 Incorrect 864 ms 27128 KB Output isn't correct
64 Incorrect 929 ms 28456 KB Output isn't correct
65 Incorrect 914 ms 26936 KB Output isn't correct
66 Incorrect 924 ms 26964 KB Output isn't correct
67 Correct 33 ms 2640 KB Output is correct
68 Incorrect 884 ms 27020 KB Output isn't correct
69 Incorrect 863 ms 27128 KB Output isn't correct
70 Incorrect 966 ms 28252 KB Output isn't correct
71 Incorrect 925 ms 28412 KB Output isn't correct
72 Incorrect 871 ms 26960 KB Output isn't correct
73 Runtime error 339 ms 65536 KB Execution killed with signal 9
74 Runtime error 342 ms 65536 KB Execution killed with signal 9
75 Runtime error 317 ms 65536 KB Execution killed with signal 9
76 Runtime error 310 ms 65536 KB Execution killed with signal 9
77 Runtime error 312 ms 65536 KB Execution killed with signal 9
78 Runtime error 274 ms 65536 KB Execution killed with signal 9
79 Runtime error 278 ms 65536 KB Execution killed with signal 9
80 Runtime error 264 ms 65536 KB Execution killed with signal 9
81 Runtime error 271 ms 65536 KB Execution killed with signal 9
82 Runtime error 267 ms 65536 KB Execution killed with signal 9
83 Runtime error 265 ms 65536 KB Execution killed with signal 9
84 Runtime error 276 ms 65536 KB Execution killed with signal 9
85 Runtime error 268 ms 65536 KB Execution killed with signal 9
86 Runtime error 260 ms 65536 KB Execution killed with signal 9
87 Runtime error 274 ms 65536 KB Execution killed with signal 9
88 Runtime error 257 ms 65536 KB Execution killed with signal 9
89 Runtime error 267 ms 65536 KB Execution killed with signal 9
90 Runtime error 247 ms 65536 KB Execution killed with signal 9
91 Runtime error 260 ms 65536 KB Execution killed with signal 9
92 Runtime error 262 ms 65536 KB Execution killed with signal 9