답안 #1102705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102705	2024-10-18T16:56:59 Z	salmon	Mecho (IOI09_mecho)	C++14	30 / 100	353 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){
        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

#	결과	실행 시간	메모리	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