답안 #1102707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102707	2024-10-18T17:09:27 Z	salmon	Mecho (IOI09_mecho)	C++14	4 / 100	345 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 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;
                    if(vt[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:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
mecho.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf(" %d",&S);
      |     ~~~~~^~~~~~~~~~
mecho.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |             scanf(" %c",&clst[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1

4.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	336 KB	Output isn't correct
2	Incorrect	1 ms	336 KB	Output isn't correct
3	Incorrect	1 ms	336 KB	Output isn't correct
4	Incorrect	1 ms	336 KB	Output isn't correct
5	Incorrect	1 ms	336 KB	Output isn't correct
6	Incorrect	1 ms	336 KB	Output isn't correct
7	Runtime error	245 ms	65536 KB	Execution killed with signal 9
8	Correct	1 ms	336 KB	Output is correct
9	Incorrect	1 ms	336 KB	Output isn't correct
10	Incorrect	1 ms	504 KB	Output isn't correct
11	Incorrect	1 ms	432 KB	Output isn't correct
12	Incorrect	1 ms	592 KB	Output isn't correct
13	Incorrect	1 ms	592 KB	Output isn't correct
14	Correct	3 ms	848 KB	Output is correct
15	Incorrect	1 ms	336 KB	Output isn't correct
16	Incorrect	1 ms	336 KB	Output isn't correct
17	Incorrect	1 ms	336 KB	Output isn't correct
18	Incorrect	1 ms	336 KB	Output isn't correct
19	Incorrect	1 ms	348 KB	Output isn't correct
20	Incorrect	1 ms	336 KB	Output isn't correct
21	Incorrect	1 ms	336 KB	Output isn't correct
22	Incorrect	1 ms	336 KB	Output isn't correct
23	Incorrect	1 ms	336 KB	Output isn't correct
24	Incorrect	1 ms	336 KB	Output isn't correct
25	Incorrect	1 ms	760 KB	Output isn't correct
26	Incorrect	1 ms	592 KB	Output isn't correct
27	Incorrect	1 ms	764 KB	Output isn't correct
28	Incorrect	1 ms	592 KB	Output isn't correct
29	Incorrect	1 ms	592 KB	Output isn't correct
30	Incorrect	1 ms	760 KB	Output isn't correct
31	Incorrect	1 ms	592 KB	Output isn't correct
32	Incorrect	1 ms	592 KB	Output isn't correct
33	Incorrect	6 ms	1104 KB	Output isn't correct
34	Incorrect	5 ms	1104 KB	Output isn't correct
35	Incorrect	7 ms	1280 KB	Output isn't correct
36	Incorrect	7 ms	1360 KB	Output isn't correct
37	Incorrect	7 ms	1272 KB	Output isn't correct
38	Incorrect	12 ms	1360 KB	Output isn't correct
39	Incorrect	9 ms	1528 KB	Output isn't correct
40	Incorrect	9 ms	1360 KB	Output isn't correct
41	Incorrect	10 ms	1528 KB	Output isn't correct
42	Incorrect	9 ms	1608 KB	Output isn't correct
43	Incorrect	9 ms	1784 KB	Output isn't correct
44	Incorrect	11 ms	1616 KB	Output isn't correct
45	Incorrect	12 ms	1616 KB	Output isn't correct
46	Incorrect	11 ms	1616 KB	Output isn't correct
47	Incorrect	15 ms	1616 KB	Output isn't correct
48	Incorrect	14 ms	2040 KB	Output isn't correct
49	Incorrect	14 ms	1872 KB	Output isn't correct
50	Incorrect	17 ms	1872 KB	Output isn't correct
51	Incorrect	16 ms	1776 KB	Output isn't correct
52	Incorrect	16 ms	1792 KB	Output isn't correct
53	Incorrect	20 ms	1872 KB	Output isn't correct
54	Incorrect	19 ms	1872 KB	Output isn't correct
55	Incorrect	18 ms	1884 KB	Output isn't correct
56	Incorrect	20 ms	1872 KB	Output isn't correct
57	Incorrect	18 ms	2216 KB	Output isn't correct
58	Incorrect	19 ms	2128 KB	Output isn't correct
59	Incorrect	22 ms	2120 KB	Output isn't correct
60	Incorrect	21 ms	2128 KB	Output isn't correct
61	Incorrect	21 ms	2128 KB	Output isn't correct
62	Incorrect	26 ms	2164 KB	Output isn't correct
63	Incorrect	34 ms	2128 KB	Output isn't correct
64	Incorrect	31 ms	2128 KB	Output isn't correct
65	Incorrect	31 ms	2128 KB	Output isn't correct
66	Incorrect	32 ms	2296 KB	Output isn't correct
67	Correct	31 ms	2220 KB	Output is correct
68	Incorrect	30 ms	2180 KB	Output isn't correct
69	Incorrect	25 ms	2384 KB	Output isn't correct
70	Incorrect	32 ms	2372 KB	Output isn't correct
71	Incorrect	32 ms	2384 KB	Output isn't correct
72	Incorrect	23 ms	2128 KB	Output isn't correct
73	Runtime error	314 ms	65536 KB	Execution killed with signal 9
74	Incorrect	30 ms	2356 KB	Output isn't correct
75	Runtime error	335 ms	65536 KB	Execution killed with signal 9
76	Runtime error	345 ms	65536 KB	Execution killed with signal 9
77	Runtime error	341 ms	65536 KB	Execution killed with signal 9
78	Runtime error	299 ms	65536 KB	Execution killed with signal 9
79	Incorrect	32 ms	2384 KB	Output isn't correct
80	Runtime error	310 ms	65536 KB	Execution killed with signal 9
81	Runtime error	298 ms	65536 KB	Execution killed with signal 9
82	Runtime error	297 ms	65536 KB	Execution killed with signal 9
83	Runtime error	267 ms	65536 KB	Execution killed with signal 9
84	Incorrect	32 ms	2384 KB	Output isn't correct
85	Runtime error	269 ms	65536 KB	Execution killed with signal 9
86	Runtime error	284 ms	65536 KB	Execution killed with signal 9
87	Runtime error	267 ms	65536 KB	Execution killed with signal 9
88	Runtime error	248 ms	65536 KB	Execution killed with signal 9
89	Incorrect	33 ms	2396 KB	Output isn't correct
90	Runtime error	259 ms	65536 KB	Execution killed with signal 9
91	Runtime error	256 ms	65536 KB	Execution killed with signal 9
92	Runtime error	251 ms	65536 KB	Execution killed with signal 9