oj.uz

Submission #1102705

# Submission time Handle Problem Language Result Execution time Memory
1102705 2024-10-18T16:56:59 Z salmon Mecho (IOI09_mecho) C++14
30 / 100
 353 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);
        }

        if(visited[s1][s2]){
            e = m1 - 1;
            continue;
        }

        /*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
30.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 2384 KB Output isn't correct
5 Correct 3 ms 2384 KB Output is correct
6 Correct 3 ms 2500 KB Output is correct
7 Runtime error 222 ms 65536 KB Execution killed with signal 9
8 Incorrect 4 ms 2384 KB Output isn't correct
9 Correct 4 ms 2384 KB Output is correct
10 Correct 4 ms 2384 KB Output is correct
11 Correct 4 ms 2384 KB Output is correct
12 Correct 5 ms 2384 KB Output is correct
13 Correct 118 ms 2852 KB Output is correct
14 Correct 3 ms 2640 KB Output is correct
15 Incorrect 3 ms 2384 KB Output isn't correct
16 Correct 3 ms 2384 KB Output is correct
17 Incorrect 3 ms 2384 KB Output isn't correct
18 Correct 3 ms 2384 KB Output is correct
19 Incorrect 3 ms 2384 KB Output isn't correct
20 Correct 3 ms 2608 KB Output is correct
21 Incorrect 3 ms 2384 KB Output isn't correct
22 Correct 3 ms 2384 KB Output is correct
23 Incorrect 3 ms 2384 KB Output isn't correct
24 Correct 3 ms 2384 KB Output is correct
25 Incorrect 4 ms 2384 KB Output isn't correct
26 Correct 4 ms 2504 KB Output is correct
27 Incorrect 4 ms 2384 KB Output isn't correct
28 Correct 4 ms 2384 KB Output is correct
29 Incorrect 4 ms 2384 KB Output isn't correct
30 Correct 4 ms 2384 KB Output is correct
31 Incorrect 4 ms 2556 KB Output isn't correct
32 Correct 4 ms 2384 KB Output is correct
33 Incorrect 27 ms 2504 KB Output isn't correct
34 Correct 24 ms 2384 KB Output is correct
35 Runtime error 188 ms 65536 KB Execution killed with signal 9
36 Incorrect 40 ms 2384 KB Output isn't correct
37 Correct 30 ms 2384 KB Output is correct
38 Runtime error 193 ms 65536 KB Execution killed with signal 9
39 Incorrect 41 ms 2384 KB Output isn't correct
40 Correct 41 ms 2556 KB Output is correct
41 Runtime error 184 ms 65536 KB Execution killed with signal 9
42 Incorrect 58 ms 2384 KB Output isn't correct
43 Correct 46 ms 2384 KB Output is correct
44 Runtime error 216 ms 65536 KB Execution killed with signal 9
45 Incorrect 74 ms 2384 KB Output isn't correct
46 Correct 56 ms 2384 KB Output is correct
47 Runtime error 216 ms 65536 KB Execution killed with signal 9
48 Incorrect 75 ms 2384 KB Output isn't correct
49 Correct 83 ms 2384 KB Output is correct
50 Runtime error 215 ms 65536 KB Execution killed with signal 9
51 Incorrect 85 ms 2528 KB Output isn't correct
52 Correct 83 ms 2384 KB Output is correct
53 Runtime error 219 ms 65536 KB Execution killed with signal 9
54 Incorrect 98 ms 2384 KB Output isn't correct
55 Correct 85 ms 2612 KB Output is correct
56 Runtime error 219 ms 65536 KB Execution killed with signal 9
57 Incorrect 121 ms 2640 KB Output isn't correct
58 Correct 102 ms 2640 KB Output is correct
59 Runtime error 220 ms 65536 KB Execution killed with signal 9
60 Incorrect 127 ms 2640 KB Output isn't correct
61 Correct 111 ms 2640 KB Output is correct
62 Runtime error 230 ms 65536 KB Execution killed with signal 9
63 Correct 250 ms 2708 KB Output is correct
64 Correct 291 ms 2640 KB Output is correct
65 Correct 269 ms 2640 KB Output is correct
66 Incorrect 271 ms 2640 KB Output isn't correct
67 Correct 33 ms 2640 KB Output is correct
68 Correct 250 ms 2744 KB Output is correct
69 Correct 216 ms 2640 KB Output is correct
70 Correct 248 ms 2504 KB Output is correct
71 Correct 237 ms 2736 KB Output is correct
72 Correct 251 ms 2640 KB Output is correct
73 Runtime error 334 ms 65536 KB Execution killed with signal 9
74 Runtime error 353 ms 65536 KB Execution killed with signal 9
75 Runtime error 330 ms 65536 KB Execution killed with signal 9
76 Runtime error 351 ms 65536 KB Execution killed with signal 9
77 Runtime error 345 ms 65536 KB Execution killed with signal 9
78 Runtime error 302 ms 65536 KB Execution killed with signal 9
79 Runtime error 321 ms 65536 KB Execution killed with signal 9
80 Runtime error 297 ms 65536 KB Execution killed with signal 9
81 Runtime error 293 ms 65536 KB Execution killed with signal 9
82 Runtime error 296 ms 65536 KB Execution killed with signal 9
83 Runtime error 264 ms 65536 KB Execution killed with signal 9
84 Runtime error 289 ms 65536 KB Execution killed with signal 9
85 Runtime error 288 ms 65536 KB Execution killed with signal 9
86 Runtime error 264 ms 65536 KB Execution killed with signal 9
87 Runtime error 302 ms 65536 KB Execution killed with signal 9
88 Runtime error 252 ms 65536 KB Execution killed with signal 9
89 Runtime error 268 ms 65536 KB Execution killed with signal 9
90 Runtime error 260 ms 65536 KB Execution killed with signal 9
91 Runtime error 282 ms 65536 KB Execution killed with signal 9
92 Runtime error 262 ms 65536 KB Execution killed with signal 9