답안 #969080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969080	2024-04-24T13:14:36 Z	anango	Mecho (IOI09_mecho)	C++17	57 / 100	1000 ms	25976 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 || 0) 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 || 0) freopen("input.txt","r",stdin);
    if (debug || 0) 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:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     if (debug || 0) freopen("input.txt","r",stdin);
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:87:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     if (debug || 0) freopen("output.txt","w",stdout);
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

57.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	559 ms	25700 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Execution timed out	1095 ms	348 KB	Time limit exceeded
13	Incorrect	1 ms	348 KB	Output isn't correct
14	Correct	2 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	3 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	5 ms	344 KB	Output is correct
20	Correct	2 ms	348 KB	Output is correct
21	Correct	15 ms	344 KB	Output is correct
22	Correct	8 ms	348 KB	Output is correct
23	Correct	35 ms	520 KB	Output is correct
24	Correct	21 ms	348 KB	Output is correct
25	Correct	74 ms	344 KB	Output is correct
26	Correct	50 ms	596 KB	Output is correct
27	Correct	105 ms	604 KB	Output is correct
28	Correct	65 ms	600 KB	Output is correct
29	Correct	134 ms	612 KB	Output is correct
30	Correct	89 ms	600 KB	Output is correct
31	Correct	181 ms	600 KB	Output is correct
32	Correct	120 ms	604 KB	Output is correct
33	Execution timed out	1055 ms	5512 KB	Time limit exceeded
34	Execution timed out	1062 ms	5476 KB	Time limit exceeded
35	Correct	120 ms	5312 KB	Output is correct
36	Execution timed out	1046 ms	7024 KB	Time limit exceeded
37	Execution timed out	1046 ms	6936 KB	Time limit exceeded
38	Correct	173 ms	6800 KB	Output is correct
39	Execution timed out	1012 ms	8704 KB	Time limit exceeded
40	Execution timed out	1049 ms	8660 KB	Time limit exceeded
41	Correct	204 ms	8276 KB	Output is correct
42	Execution timed out	1061 ms	10576 KB	Time limit exceeded
43	Execution timed out	1057 ms	10536 KB	Time limit exceeded
44	Correct	253 ms	10324 KB	Output is correct
45	Execution timed out	1076 ms	12540 KB	Time limit exceeded
46	Execution timed out	1044 ms	12592 KB	Time limit exceeded
47	Correct	348 ms	12608 KB	Output is correct
48	Execution timed out	1029 ms	14688 KB	Time limit exceeded
49	Execution timed out	1056 ms	14880 KB	Time limit exceeded
50	Correct	414 ms	14644 KB	Output is correct
51	Execution timed out	1022 ms	17440 KB	Time limit exceeded
52	Execution timed out	1067 ms	17312 KB	Time limit exceeded
53	Correct	497 ms	17104 KB	Output is correct
54	Execution timed out	1053 ms	19924 KB	Time limit exceeded
55	Execution timed out	1102 ms	20004 KB	Time limit exceeded
56	Correct	591 ms	19844 KB	Output is correct
57	Execution timed out	1067 ms	22916 KB	Time limit exceeded
58	Execution timed out	1076 ms	23076 KB	Time limit exceeded
59	Correct	664 ms	22616 KB	Output is correct
60	Execution timed out	1049 ms	25904 KB	Time limit exceeded
61	Execution timed out	1059 ms	25936 KB	Time limit exceeded
62	Correct	852 ms	25952 KB	Output is correct
63	Incorrect	384 ms	25636 KB	Output isn't correct
64	Incorrect	736 ms	25828 KB	Output isn't correct
65	Incorrect	679 ms	25648 KB	Output isn't correct
66	Incorrect	571 ms	25752 KB	Output isn't correct
67	Correct	466 ms	25656 KB	Output is correct
68	Incorrect	207 ms	25720 KB	Output isn't correct
69	Incorrect	224 ms	25676 KB	Output isn't correct
70	Incorrect	207 ms	25720 KB	Output isn't correct
71	Incorrect	168 ms	25752 KB	Output isn't correct
72	Incorrect	124 ms	25740 KB	Output isn't correct
73	Incorrect	206 ms	25856 KB	Output isn't correct
74	Correct	366 ms	25956 KB	Output is correct
75	Correct	443 ms	25756 KB	Output is correct
76	Correct	403 ms	25768 KB	Output is correct
77	Correct	431 ms	25860 KB	Output is correct
78	Correct	483 ms	25780 KB	Output is correct
79	Correct	350 ms	25920 KB	Output is correct
80	Correct	377 ms	25724 KB	Output is correct
81	Correct	419 ms	25976 KB	Output is correct
82	Correct	376 ms	25780 KB	Output is correct
83	Correct	599 ms	25756 KB	Output is correct
84	Correct	413 ms	25732 KB	Output is correct
85	Correct	457 ms	25736 KB	Output is correct
86	Correct	536 ms	25848 KB	Output is correct
87	Correct	473 ms	25716 KB	Output is correct
88	Correct	567 ms	25964 KB	Output is correct
89	Correct	557 ms	25708 KB	Output is correct
90	Correct	582 ms	25692 KB	Output is correct
91	Correct	543 ms	25700 KB	Output is correct
92	Correct	551 ms	25748 KB	Output is correct