답안 #969073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969073	2024-04-24T13:06:31 Z	anango	Mecho (IOI09_mecho)	C++17	39 / 100	799 ms	26028 KB

mecho

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,s;
vector<vector<int>> dist;
vector<vector<int>> grid;
pair<int,int> start;
pair<int,int> finish;


int debug=0;
int INF=1000000007;
int gval(pair<int,int> cell) {
    return grid[cell.first][cell.second];
}

bool bounds(pair<int,int> cell) {
    return 0<=cell.first && cell.first<n && 0<=cell.second && cell.second<n;
}

vector<pair<int,int>> getnei(pair<int,int> st) {
    if (!(gval(st)==0)) {
        return {};
    }
    vector<pair<int,int>> V={{st.first-1,st.second},{st.first+1,st.second},{st.first,st.second+1},{st.first,st.second-1}};
    vector<pair<int,int>> ans;
    for (auto nei:V) {
        if (bounds(nei) && ((gval(nei)==0) || gval(nei)==2)) {
            ans.push_back(nei);
        }
    }
    return ans;
}

bool BSTA(int time) {
    //returns whether it can be done after waiting this time
    vector<vector<int>> distance(n,vector<int>(n,INF));
    vector<vector<int>> proc(n,vector<int>(n,0));
    deque<pair<int,int>> visited={start};
    distance[start.first][start.second] = 0;
    while (visited.size()) {
        pair<int,int> fi=visited[0];
        visited.pop_front();
        if (proc[fi.first][fi.second]) {
            continue;
        }
        proc[fi.first][fi.second] = 1;
        for (auto j:getnei(fi)) {
            int bdist=time+(distance[fi.first][fi.second]+1)/s; 
            //it's the total number of steps the honey has to walk to reach this cell
            if(debug) cout << fi.first << " " << fi.second << " " << j.first << " " << j.second << " "<<bdist << " " <<dist[fi.first][fi.second] << endl;
            if (bdist>=(dist[j.first][j.second])) {
                continue;
            }
            distance[j.first][j.second] = min(distance[j.first][j.second],distance[fi.first][fi.second]+1);
            visited.push_back(j);
        }
    }
    if(debug) cout << "BSTA TRYING METHOD CALCULATION TO FIND THE ANSWER" << " " << time << endl;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if(debug) cout << distance[i][j] <<" ";
        }
        if(debug) cout << endl;
    }
    return distance[finish.first][finish.second] < 3*n;
    
}


vector<pair<int,int>> adjlistbee(pair<int,int> st) {
    if (!(gval(st)==0 || gval(st)==3)) {
        return {};
    }
    vector<pair<int,int>> V={{st.first-1,st.second},{st.first+1,st.second},{st.first,st.second+1},{st.first,st.second-1}};
    vector<pair<int,int>> ans;
    for (auto nei:V) {
        if (bounds(nei) && gval(nei)==0) {
            ans.push_back(nei);
        }
    }
    return ans;
}

signed main() {
    if (debug) freopen("input.txt","r",stdin);
    if (debug) freopen("output.txt","w",stdout);
    cin >> n >> s;
    dist=vector<vector<int>>(n,vector<int>(n,INF));
    grid=vector<vector<int>>(n,vector<int>(n,-1));
    vector<vector<int>> proc(n,vector<int>(n,0));
    vector<pair<int,int>> hives;
    deque<pair<int,int>> visited;
    for (int i=0; i<n; i++) {
        string st;
        cin >> st;
        //if(debug) cout << st << endl;
        for (int j=0; j<n; j++) {
            //if(debug) cout << i <<" " << j << " " << st[j] << endl;
            int ans;
            if (st[j]=='G') {
                ans=0;
            }
            else if (st[j]=='M') {
                ans=0;
                start={i,j};
            }
            else if (st[j]=='D') {
                ans=2;
                finish={i,j};
            }
            else if (st[j]=='T') {
                ans=1;
                
            }
            else {
                //assert(st[j]=='H');
                ans=3;
                hives.push_back({i,j});
                dist[i][j] = 0;
                visited.push_back({i,j});
            }
            grid[i][j] = ans;
            //if(debug) cout << i << " " << j << endl;
        }
    }
    //a cell is available to bees if the cell is 0 or 3, 3 denotes starting hives
    //a cell is available to mecho if the dist condition holds and the cell isn't a tree
    while (visited.size()) {
        pair<int,int> fi=visited[0];
        visited.pop_front();
        if (proc[fi.first][fi.second]) {
            continue;
        }
        proc[fi.first][fi.second] = 1;
        for (auto j:adjlistbee(fi)) {
            dist[j.first][j.second] = min(dist[j.first][j.second],dist[fi.first][fi.second]+1);
            visited.push_back(j);
        }
    }
    if(debug) cout << "DISTS"<< endl;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            //cout << dist[i][j] <<" ";
        }
        if(debug) cout << endl;
    }
    


    int l=0;
    int r=n*3;
    while (l<r) {
        int m=(l+r)/2;
        if (!BSTA(m)) {
            l=l;
            r=m;
        }
        else {
            l=m+1;
            r=r;
        }
    }
    if (l==0 && !BSTA(l)) {
        cout << -1 << endl;
        return 0;
    }
    if (l>0 && !BSTA(l)) {
        l--;
    }
    if (BSTA(l+1)) {
        l++;
    }
    if (l==0 && !BSTA(l)) {
        if(debug) cout << -1 << endl;
        return 0;
    }
    cout << l << endl;

}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:86:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     if (debug) freopen("input.txt","r",stdin);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:87:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     if (debug) freopen("output.txt","w",stdout);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

39.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	503 ms	25728 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Incorrect	1 ms	348 KB	Output isn't correct
13	Incorrect	1 ms	348 KB	Output isn't correct
14	Correct	2 ms	348 KB	Output is correct
15	Incorrect	0 ms	348 KB	Output isn't correct
16	Incorrect	0 ms	348 KB	Output isn't correct
17	Incorrect	1 ms	348 KB	Output isn't correct
18	Incorrect	1 ms	348 KB	Output isn't correct
19	Incorrect	1 ms	348 KB	Output isn't correct
20	Incorrect	1 ms	348 KB	Output isn't correct
21	Incorrect	1 ms	348 KB	Output isn't correct
22	Incorrect	1 ms	348 KB	Output isn't correct
23	Incorrect	1 ms	348 KB	Output isn't correct
24	Incorrect	2 ms	348 KB	Output isn't correct
25	Incorrect	1 ms	348 KB	Output isn't correct
26	Incorrect	2 ms	348 KB	Output isn't correct
27	Incorrect	3 ms	376 KB	Output isn't correct
28	Incorrect	2 ms	604 KB	Output isn't correct
29	Incorrect	2 ms	604 KB	Output isn't correct
30	Incorrect	2 ms	604 KB	Output isn't correct
31	Incorrect	2 ms	604 KB	Output isn't correct
32	Incorrect	2 ms	604 KB	Output isn't correct
33	Incorrect	45 ms	5272 KB	Output isn't correct
34	Incorrect	69 ms	5268 KB	Output isn't correct
35	Correct	109 ms	5288 KB	Output is correct
36	Incorrect	64 ms	6940 KB	Output isn't correct
37	Incorrect	91 ms	6764 KB	Output isn't correct
38	Correct	159 ms	6800 KB	Output is correct
39	Incorrect	71 ms	8280 KB	Output isn't correct
40	Incorrect	124 ms	8280 KB	Output isn't correct
41	Correct	183 ms	8452 KB	Output is correct
42	Incorrect	94 ms	10312 KB	Output isn't correct
43	Incorrect	148 ms	10172 KB	Output isn't correct
44	Correct	235 ms	10412 KB	Output is correct
45	Incorrect	107 ms	12364 KB	Output isn't correct
46	Incorrect	177 ms	12344 KB	Output isn't correct
47	Correct	328 ms	12620 KB	Output is correct
48	Incorrect	128 ms	14640 KB	Output isn't correct
49	Incorrect	209 ms	14616 KB	Output isn't correct
50	Correct	385 ms	14624 KB	Output is correct
51	Incorrect	151 ms	17092 KB	Output isn't correct
52	Incorrect	249 ms	17292 KB	Output isn't correct
53	Correct	428 ms	17036 KB	Output is correct
54	Incorrect	184 ms	19768 KB	Output isn't correct
55	Incorrect	309 ms	19760 KB	Output isn't correct
56	Correct	551 ms	19912 KB	Output is correct
57	Incorrect	222 ms	22588 KB	Output isn't correct
58	Incorrect	355 ms	22800 KB	Output isn't correct
59	Correct	612 ms	22608 KB	Output is correct
60	Incorrect	260 ms	25816 KB	Output isn't correct
61	Incorrect	399 ms	25640 KB	Output isn't correct
62	Correct	799 ms	25864 KB	Output is correct
63	Incorrect	422 ms	25704 KB	Output isn't correct
64	Incorrect	734 ms	25648 KB	Output isn't correct
65	Incorrect	665 ms	25652 KB	Output isn't correct
66	Incorrect	527 ms	25660 KB	Output isn't correct
67	Correct	423 ms	25924 KB	Output is correct
68	Incorrect	204 ms	25716 KB	Output isn't correct
69	Incorrect	221 ms	25676 KB	Output isn't correct
70	Incorrect	189 ms	25712 KB	Output isn't correct
71	Incorrect	162 ms	25728 KB	Output isn't correct
72	Incorrect	134 ms	25772 KB	Output isn't correct
73	Incorrect	175 ms	25812 KB	Output isn't correct
74	Correct	337 ms	25772 KB	Output is correct
75	Correct	411 ms	25764 KB	Output is correct
76	Correct	376 ms	25772 KB	Output is correct
77	Correct	379 ms	25784 KB	Output is correct
78	Correct	446 ms	25756 KB	Output is correct
79	Correct	323 ms	26028 KB	Output is correct
80	Correct	368 ms	25740 KB	Output is correct
81	Correct	386 ms	25776 KB	Output is correct
82	Correct	346 ms	25700 KB	Output is correct
83	Correct	519 ms	25776 KB	Output is correct
84	Correct	390 ms	25760 KB	Output is correct
85	Correct	415 ms	25712 KB	Output is correct
86	Correct	496 ms	25776 KB	Output is correct
87	Correct	435 ms	25748 KB	Output is correct
88	Correct	574 ms	25724 KB	Output is correct
89	Correct	528 ms	25912 KB	Output is correct
90	Correct	537 ms	25732 KB	Output is correct
91	Correct	496 ms	25696 KB	Output is correct
92	Correct	517 ms	25932 KB	Output is correct