답안 #969070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969070	2024-04-24T13:04:39 Z	anango	Mecho (IOI09_mecho)	C++17	57 / 100	1000 ms	26484 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;
    }
    while (l>0 && !BSTA(l)) {
        l--;
    }
    while (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

57.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	436 KB	Output is correct
7	Correct	620 ms	25748 KB	Output is correct
8	Correct	1 ms	352 KB	Output is correct
9	Correct	0 ms	432 KB	Output is correct
10	Correct	1 ms	436 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Execution timed out	1096 ms	360 KB	Time limit exceeded
13	Incorrect	1 ms	360 KB	Output isn't correct
14	Correct	2 ms	360 KB	Output is correct
15	Correct	1 ms	356 KB	Output is correct
16	Correct	1 ms	360 KB	Output is correct
17	Correct	3 ms	480 KB	Output is correct
18	Correct	2 ms	356 KB	Output is correct
19	Correct	5 ms	352 KB	Output is correct
20	Correct	2 ms	356 KB	Output is correct
21	Correct	23 ms	356 KB	Output is correct
22	Correct	8 ms	352 KB	Output is correct
23	Correct	36 ms	528 KB	Output is correct
24	Correct	23 ms	356 KB	Output is correct
25	Correct	83 ms	580 KB	Output is correct
26	Correct	46 ms	348 KB	Output is correct
27	Correct	110 ms	600 KB	Output is correct
28	Correct	66 ms	604 KB	Output is correct
29	Correct	151 ms	848 KB	Output is correct
30	Correct	102 ms	620 KB	Output is correct
31	Correct	227 ms	604 KB	Output is correct
32	Correct	121 ms	664 KB	Output is correct
33	Execution timed out	1033 ms	5600 KB	Time limit exceeded
34	Execution timed out	1036 ms	5424 KB	Time limit exceeded
35	Correct	120 ms	5368 KB	Output is correct
36	Execution timed out	1029 ms	7072 KB	Time limit exceeded
37	Execution timed out	1067 ms	7092 KB	Time limit exceeded
38	Correct	171 ms	6860 KB	Output is correct
39	Execution timed out	1068 ms	8956 KB	Time limit exceeded
40	Execution timed out	1060 ms	8648 KB	Time limit exceeded
41	Correct	213 ms	8628 KB	Output is correct
42	Execution timed out	1046 ms	10568 KB	Time limit exceeded
43	Execution timed out	1014 ms	10608 KB	Time limit exceeded
44	Correct	249 ms	10516 KB	Output is correct
45	Execution timed out	1045 ms	12792 KB	Time limit exceeded
46	Execution timed out	1033 ms	12832 KB	Time limit exceeded
47	Correct	348 ms	12604 KB	Output is correct
48	Execution timed out	1018 ms	14916 KB	Time limit exceeded
49	Execution timed out	1055 ms	15116 KB	Time limit exceeded
50	Correct	432 ms	14844 KB	Output is correct
51	Execution timed out	1057 ms	18040 KB	Time limit exceeded
52	Execution timed out	1016 ms	17416 KB	Time limit exceeded
53	Correct	481 ms	17420 KB	Output is correct
54	Execution timed out	1050 ms	20360 KB	Time limit exceeded
55	Execution timed out	1059 ms	20240 KB	Time limit exceeded
56	Correct	601 ms	20092 KB	Output is correct
57	Execution timed out	1047 ms	23092 KB	Time limit exceeded
58	Execution timed out	1102 ms	23388 KB	Time limit exceeded
59	Correct	647 ms	22868 KB	Output is correct
60	Execution timed out	1025 ms	26480 KB	Time limit exceeded
61	Execution timed out	1051 ms	26344 KB	Time limit exceeded
62	Correct	879 ms	26224 KB	Output is correct
63	Incorrect	401 ms	26056 KB	Output isn't correct
64	Incorrect	740 ms	26020 KB	Output isn't correct
65	Incorrect	663 ms	26120 KB	Output isn't correct
66	Incorrect	573 ms	26040 KB	Output isn't correct
67	Correct	436 ms	26068 KB	Output is correct
68	Incorrect	216 ms	26156 KB	Output isn't correct
69	Incorrect	237 ms	26140 KB	Output isn't correct
70	Incorrect	181 ms	26164 KB	Output isn't correct
71	Incorrect	160 ms	26192 KB	Output isn't correct
72	Incorrect	131 ms	26184 KB	Output isn't correct
73	Incorrect	230 ms	26276 KB	Output isn't correct
74	Correct	354 ms	26192 KB	Output is correct
75	Correct	485 ms	26484 KB	Output is correct
76	Correct	402 ms	26144 KB	Output is correct
77	Correct	425 ms	26328 KB	Output is correct
78	Correct	447 ms	26184 KB	Output is correct
79	Correct	354 ms	26440 KB	Output is correct
80	Correct	413 ms	26104 KB	Output is correct
81	Correct	412 ms	26096 KB	Output is correct
82	Correct	368 ms	26156 KB	Output is correct
83	Correct	588 ms	26236 KB	Output is correct
84	Correct	445 ms	26016 KB	Output is correct
85	Correct	482 ms	26368 KB	Output is correct
86	Correct	528 ms	26212 KB	Output is correct
87	Correct	478 ms	26188 KB	Output is correct
88	Correct	602 ms	26328 KB	Output is correct
89	Correct	608 ms	26156 KB	Output is correct
90	Correct	569 ms	26144 KB	Output is correct
91	Correct	603 ms	26356 KB	Output is correct
92	Correct	578 ms	26372 KB	Output is correct