oj.uz

Submission #1102703

# Submission time Handle Problem Language Result Execution time Memory
1102703 2024-10-18T16:21:34 Z salmon Mecho (IOI09_mecho) C++14
19 / 100
 358 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'){
                visited[i][j] = true;
                vt[i][j] = true;
                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] = false;

    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'){
                    visited[i][j] = true;
                    q[1].push({i,j});
                }
                else if(clst[i][j] == 'D'){
                    visited[i][j] = true;
                }
            }
        }

        cq = 0;
        cm = 0;

        spreadhoney(1);

        vt[s1][s2] = false;

        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
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT
*/

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
19.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2388 KB Output isn't correct
2 Incorrect 4 ms 2388 KB Output isn't correct
3 Incorrect 4 ms 2388 KB Output isn't correct
4 Incorrect 4 ms 2388 KB Output isn't correct
5 Correct 3 ms 2388 KB Output is correct
6 Correct 3 ms 2512 KB Output is correct
7 Runtime error 240 ms 65536 KB Execution killed with signal 9
8 Incorrect 5 ms 2388 KB Output isn't correct
9 Correct 5 ms 2388 KB Output is correct
10 Correct 5 ms 2492 KB Output is correct
11 Correct 7 ms 2552 KB Output is correct
12 Incorrect 43 ms 2388 KB Output isn't correct
13 Incorrect 108 ms 2916 KB Output isn't correct
14 Correct 3 ms 2644 KB Output is correct
15 Incorrect 4 ms 2388 KB Output isn't correct
16 Correct 4 ms 2388 KB Output is correct
17 Incorrect 4 ms 2388 KB Output isn't correct
18 Correct 3 ms 2508 KB Output is correct
19 Incorrect 4 ms 2388 KB Output isn't correct
20 Correct 3 ms 2552 KB Output is correct
21 Incorrect 6 ms 2512 KB Output isn't correct
22 Correct 3 ms 2388 KB Output is correct
23 Incorrect 3 ms 2508 KB Output isn't correct
24 Correct 3 ms 2388 KB Output is correct
25 Incorrect 4 ms 2552 KB Output isn't correct
26 Correct 6 ms 2388 KB Output is correct
27 Incorrect 4 ms 2388 KB Output isn't correct
28 Correct 4 ms 2512 KB Output is correct
29 Incorrect 4 ms 2508 KB Output isn't correct
30 Correct 4 ms 2388 KB Output is correct
31 Incorrect 4 ms 2388 KB Output isn't correct
32 Correct 4 ms 2388 KB Output is correct
33 Incorrect 30 ms 2624 KB Output isn't correct
34 Correct 28 ms 2616 KB Output is correct
35 Runtime error 198 ms 65536 KB Execution killed with signal 9
36 Incorrect 37 ms 2644 KB Output isn't correct
37 Correct 33 ms 2644 KB Output is correct
38 Runtime error 203 ms 65536 KB Execution killed with signal 9
39 Incorrect 46 ms 2644 KB Output isn't correct
40 Correct 46 ms 2644 KB Output is correct
41 Runtime error 204 ms 65536 KB Execution killed with signal 9
42 Incorrect 54 ms 2740 KB Output isn't correct
43 Correct 49 ms 2740 KB Output is correct
44 Runtime error 197 ms 65536 KB Execution killed with signal 9
45 Incorrect 59 ms 2644 KB Output isn't correct
46 Correct 52 ms 2804 KB Output is correct
47 Runtime error 190 ms 65536 KB Execution killed with signal 9
48 Incorrect 76 ms 2872 KB Output isn't correct
49 Correct 65 ms 3064 KB Output is correct
50 Runtime error 210 ms 65536 KB Execution killed with signal 9
51 Incorrect 82 ms 2900 KB Output isn't correct
52 Correct 72 ms 3008 KB Output is correct
53 Runtime error 200 ms 65536 KB Execution killed with signal 9
54 Incorrect 94 ms 3100 KB Output isn't correct
55 Correct 88 ms 3104 KB Output is correct
56 Runtime error 203 ms 65536 KB Execution killed with signal 9
57 Incorrect 108 ms 3220 KB Output isn't correct
58 Correct 107 ms 3216 KB Output is correct
59 Runtime error 229 ms 65536 KB Execution killed with signal 9
60 Incorrect 132 ms 3340 KB Output isn't correct
61 Correct 113 ms 3156 KB Output is correct
62 Runtime error 221 ms 65536 KB Execution killed with signal 9
63 Correct 257 ms 3156 KB Output is correct
64 Correct 295 ms 3156 KB Output is correct
65 Correct 290 ms 3156 KB Output is correct
66 Incorrect 280 ms 3344 KB Output isn't correct
67 Correct 33 ms 3144 KB Output is correct
68 Correct 245 ms 3356 KB Output is correct
69 Correct 219 ms 3156 KB Output is correct
70 Correct 266 ms 3340 KB Output is correct
71 Correct 261 ms 3248 KB Output is correct
72 Incorrect 271 ms 3404 KB Output isn't correct
73 Runtime error 340 ms 65536 KB Execution killed with signal 9
74 Runtime error 350 ms 65536 KB Execution killed with signal 9
75 Runtime error 338 ms 65536 KB Execution killed with signal 9
76 Runtime error 358 ms 65536 KB Execution killed with signal 9
77 Runtime error 348 ms 65536 KB Execution killed with signal 9
78 Runtime error 294 ms 65536 KB Execution killed with signal 9
79 Runtime error 288 ms 65536 KB Execution killed with signal 9
80 Runtime error 263 ms 65536 KB Execution killed with signal 9
81 Runtime error 299 ms 65536 KB Execution killed with signal 9
82 Runtime error 287 ms 65536 KB Execution killed with signal 9
83 Runtime error 244 ms 65536 KB Execution killed with signal 9
84 Runtime error 266 ms 65536 KB Execution killed with signal 9
85 Runtime error 237 ms 65536 KB Execution killed with signal 9
86 Runtime error 261 ms 65536 KB Execution killed with signal 9
87 Runtime error 280 ms 65536 KB Execution killed with signal 9
88 Runtime error 278 ms 65536 KB Execution killed with signal 9
89 Runtime error 266 ms 65536 KB Execution killed with signal 9
90 Runtime error 261 ms 65536 KB Execution killed with signal 9
91 Runtime error 273 ms 65536 KB Execution killed with signal 9
92 Runtime error 247 ms 65536 KB Execution killed with signal 9