답안 #1102866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102866	2024-10-19T05:41:18 Z	salmon	Mecho (IOI09_mecho)	C++14	54 / 100	374 ms	3416 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;

        if(visited[i][j]) continue;
        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){
        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
THGGGGG
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

54.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	336 KB	Output isn't correct
2	Incorrect	4 ms	336 KB	Output isn't correct
3	Incorrect	3 ms	336 KB	Output isn't correct
4	Incorrect	3 ms	336 KB	Output isn't correct
5	Correct	3 ms	336 KB	Output is correct
6	Correct	3 ms	336 KB	Output is correct
7	Correct	350 ms	3024 KB	Output is correct
8	Incorrect	4 ms	336 KB	Output isn't correct
9	Correct	3 ms	488 KB	Output is correct
10	Correct	3 ms	336 KB	Output is correct
11	Correct	4 ms	660 KB	Output is correct
12	Correct	4 ms	592 KB	Output is correct
13	Correct	4 ms	336 KB	Output is correct
14	Correct	1 ms	592 KB	Output is correct
15	Incorrect	4 ms	336 KB	Output isn't correct
16	Correct	4 ms	336 KB	Output is correct
17	Incorrect	4 ms	348 KB	Output isn't correct
18	Correct	4 ms	336 KB	Output is correct
19	Incorrect	3 ms	528 KB	Output isn't correct
20	Correct	3 ms	336 KB	Output is correct
21	Incorrect	4 ms	548 KB	Output isn't correct
22	Correct	4 ms	336 KB	Output is correct
23	Incorrect	4 ms	336 KB	Output isn't correct
24	Correct	4 ms	336 KB	Output is correct
25	Incorrect	4 ms	764 KB	Output isn't correct
26	Correct	4 ms	592 KB	Output is correct
27	Incorrect	4 ms	592 KB	Output isn't correct
28	Correct	4 ms	592 KB	Output is correct
29	Incorrect	4 ms	592 KB	Output isn't correct
30	Correct	4 ms	592 KB	Output is correct
31	Incorrect	4 ms	632 KB	Output isn't correct
32	Correct	5 ms	592 KB	Output is correct
33	Incorrect	32 ms	1104 KB	Output isn't correct
34	Correct	26 ms	1104 KB	Output is correct
35	Correct	48 ms	1292 KB	Output is correct
36	Incorrect	38 ms	1360 KB	Output isn't correct
37	Correct	33 ms	1360 KB	Output is correct
38	Correct	62 ms	1360 KB	Output is correct
39	Incorrect	43 ms	1360 KB	Output isn't correct
40	Correct	38 ms	1360 KB	Output is correct
41	Correct	82 ms	1720 KB	Output is correct
42	Incorrect	57 ms	1784 KB	Output isn't correct
43	Correct	45 ms	1616 KB	Output is correct
44	Correct	98 ms	1616 KB	Output is correct
45	Incorrect	60 ms	1784 KB	Output isn't correct
46	Correct	54 ms	1872 KB	Output is correct
47	Correct	113 ms	1628 KB	Output is correct
48	Incorrect	79 ms	1872 KB	Output isn't correct
49	Correct	68 ms	2056 KB	Output is correct
50	Correct	134 ms	1872 KB	Output is correct
51	Incorrect	85 ms	1888 KB	Output isn't correct
52	Correct	75 ms	1888 KB	Output is correct
53	Correct	167 ms	1872 KB	Output is correct
54	Incorrect	98 ms	1872 KB	Output isn't correct
55	Correct	87 ms	2384 KB	Output is correct
56	Correct	190 ms	2116 KB	Output is correct
57	Incorrect	111 ms	2128 KB	Output isn't correct
58	Correct	106 ms	2128 KB	Output is correct
59	Correct	225 ms	2244 KB	Output is correct
60	Incorrect	133 ms	2644 KB	Output isn't correct
61	Correct	120 ms	2128 KB	Output is correct
62	Correct	252 ms	2812 KB	Output is correct
63	Correct	240 ms	2128 KB	Output is correct
64	Correct	283 ms	2128 KB	Output is correct
65	Correct	264 ms	2136 KB	Output is correct
66	Incorrect	263 ms	2128 KB	Output isn't correct
67	Correct	32 ms	2348 KB	Output is correct
68	Correct	254 ms	2384 KB	Output is correct
69	Correct	218 ms	2888 KB	Output is correct
70	Correct	252 ms	2384 KB	Output is correct
71	Correct	244 ms	2888 KB	Output is correct
72	Correct	250 ms	2120 KB	Output is correct
73	Correct	266 ms	2896 KB	Output is correct
74	Correct	346 ms	3220 KB	Output is correct
75	Correct	361 ms	2924 KB	Output is correct
76	Correct	359 ms	2896 KB	Output is correct
77	Correct	346 ms	3408 KB	Output is correct
78	Correct	35 ms	3152 KB	Output is correct
79	Correct	305 ms	3164 KB	Output is correct
80	Correct	323 ms	3408 KB	Output is correct
81	Correct	331 ms	3152 KB	Output is correct
82	Correct	327 ms	3376 KB	Output is correct
83	Correct	330 ms	3296 KB	Output is correct
84	Correct	357 ms	3336 KB	Output is correct
85	Correct	368 ms	3416 KB	Output is correct
86	Correct	374 ms	2888 KB	Output is correct
87	Correct	332 ms	3144 KB	Output is correct
88	Correct	341 ms	2684 KB	Output is correct
89	Correct	357 ms	3152 KB	Output is correct
90	Correct	350 ms	2640 KB	Output is correct
91	Correct	364 ms	3152 KB	Output is correct
92	Correct	332 ms	3192 KB	Output is correct