답안 #1102706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102706	2024-10-18T17:05:37 Z	salmon	Mecho (IOI09_mecho)	C++14	4 / 100	328 ms	65536 KB

mecho

#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 || true){
        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

4.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	2384 KB	Output isn't correct
2	Incorrect	1 ms	2456 KB	Output isn't correct
3	Incorrect	1 ms	2384 KB	Output isn't correct
4	Incorrect	1 ms	2384 KB	Output isn't correct
5	Incorrect	1 ms	2384 KB	Output isn't correct
6	Incorrect	1 ms	2384 KB	Output isn't correct
7	Runtime error	211 ms	65536 KB	Execution killed with signal 9
8	Correct	1 ms	2384 KB	Output is correct
9	Incorrect	1 ms	2384 KB	Output isn't correct
10	Incorrect	1 ms	2384 KB	Output isn't correct
11	Incorrect	1 ms	2552 KB	Output isn't correct
12	Incorrect	1 ms	2384 KB	Output isn't correct
13	Incorrect	1 ms	2556 KB	Output isn't correct
14	Correct	2 ms	2640 KB	Output is correct
15	Incorrect	1 ms	2384 KB	Output isn't correct
16	Incorrect	1 ms	2384 KB	Output isn't correct
17	Incorrect	1 ms	2384 KB	Output isn't correct
18	Incorrect	1 ms	2384 KB	Output isn't correct
19	Incorrect	1 ms	2384 KB	Output isn't correct
20	Incorrect	1 ms	2384 KB	Output isn't correct
21	Incorrect	1 ms	2384 KB	Output isn't correct
22	Incorrect	1 ms	2384 KB	Output isn't correct
23	Incorrect	1 ms	2384 KB	Output isn't correct
24	Incorrect	1 ms	2384 KB	Output isn't correct
25	Incorrect	1 ms	2552 KB	Output isn't correct
26	Incorrect	1 ms	2384 KB	Output isn't correct
27	Incorrect	1 ms	2384 KB	Output isn't correct
28	Incorrect	1 ms	2384 KB	Output isn't correct
29	Incorrect	1 ms	2556 KB	Output isn't correct
30	Incorrect	1 ms	2384 KB	Output isn't correct
31	Incorrect	1 ms	2384 KB	Output isn't correct
32	Incorrect	1 ms	2384 KB	Output isn't correct
33	Incorrect	5 ms	2384 KB	Output isn't correct
34	Incorrect	5 ms	2384 KB	Output isn't correct
35	Incorrect	7 ms	2640 KB	Output isn't correct
36	Incorrect	6 ms	2508 KB	Output isn't correct
37	Incorrect	6 ms	2384 KB	Output isn't correct
38	Incorrect	9 ms	2640 KB	Output isn't correct
39	Incorrect	7 ms	2504 KB	Output isn't correct
40	Incorrect	9 ms	2552 KB	Output isn't correct
41	Incorrect	13 ms	2640 KB	Output isn't correct
42	Incorrect	9 ms	2384 KB	Output isn't correct
43	Incorrect	9 ms	2384 KB	Output isn't correct
44	Incorrect	13 ms	2752 KB	Output isn't correct
45	Incorrect	14 ms	2384 KB	Output isn't correct
46	Incorrect	10 ms	2384 KB	Output isn't correct
47	Incorrect	16 ms	2808 KB	Output isn't correct
48	Incorrect	14 ms	2552 KB	Output isn't correct
49	Incorrect	13 ms	2552 KB	Output isn't correct
50	Incorrect	21 ms	2928 KB	Output isn't correct
51	Incorrect	15 ms	2384 KB	Output isn't correct
52	Incorrect	15 ms	2504 KB	Output isn't correct
53	Incorrect	21 ms	2876 KB	Output isn't correct
54	Incorrect	18 ms	2384 KB	Output isn't correct
55	Incorrect	17 ms	2384 KB	Output isn't correct
56	Incorrect	24 ms	2980 KB	Output isn't correct
57	Incorrect	20 ms	2652 KB	Output isn't correct
58	Incorrect	19 ms	2504 KB	Output isn't correct
59	Incorrect	38 ms	2992 KB	Output isn't correct
60	Incorrect	25 ms	2568 KB	Output isn't correct
61	Incorrect	21 ms	2584 KB	Output isn't correct
62	Incorrect	32 ms	3152 KB	Output isn't correct
63	Incorrect	37 ms	2632 KB	Output isn't correct
64	Incorrect	36 ms	2640 KB	Output isn't correct
65	Incorrect	41 ms	2640 KB	Output isn't correct
66	Incorrect	35 ms	2640 KB	Output isn't correct
67	Correct	32 ms	2656 KB	Output is correct
68	Incorrect	32 ms	2640 KB	Output isn't correct
69	Incorrect	28 ms	2640 KB	Output isn't correct
70	Incorrect	35 ms	2640 KB	Output isn't correct
71	Incorrect	34 ms	2640 KB	Output isn't correct
72	Incorrect	27 ms	2640 KB	Output isn't correct
73	Runtime error	328 ms	65536 KB	Execution killed with signal 9
74	Incorrect	47 ms	3516 KB	Output isn't correct
75	Runtime error	295 ms	65536 KB	Execution killed with signal 9
76	Runtime error	294 ms	65536 KB	Execution killed with signal 9
77	Runtime error	304 ms	65536 KB	Execution killed with signal 9
78	Runtime error	259 ms	65536 KB	Execution killed with signal 9
79	Incorrect	40 ms	3408 KB	Output isn't correct
80	Runtime error	254 ms	65536 KB	Execution killed with signal 9
81	Runtime error	257 ms	65536 KB	Execution killed with signal 9
82	Runtime error	257 ms	65536 KB	Execution killed with signal 9
83	Runtime error	260 ms	65536 KB	Execution killed with signal 9
84	Incorrect	40 ms	3416 KB	Output isn't correct
85	Runtime error	251 ms	65536 KB	Execution killed with signal 9
86	Runtime error	257 ms	65536 KB	Execution killed with signal 9
87	Runtime error	291 ms	65536 KB	Execution killed with signal 9
88	Runtime error	241 ms	65536 KB	Execution killed with signal 9
89	Incorrect	41 ms	3420 KB	Output isn't correct
90	Runtime error	248 ms	65536 KB	Execution killed with signal 9
91	Runtime error	264 ms	65536 KB	Execution killed with signal 9
92	Runtime error	247 ms	65536 KB	Execution killed with signal 9