답안 #969045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969045	2024-04-24T12:22:17 Z	anango	Mecho (IOI09_mecho)	C++17	29 / 100	1000 ms	26440 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 || 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) || 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=(distance[fi.first][fi.second]+s-1)/s + time; //ceil(distance/S)+T
            if(debug) cout << fi.first << " " << fi.second << " " << j.first << " " << j.second << " "<<bdist << " " <<dist[fi.first][fi.second] << endl;
            if (bdist>=(dist[fi.first][fi.second]+1)) {
                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)) {
        if(debug) 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:85:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     if (debug) freopen("input.txt","r",stdin);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
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("output.txt","w",stdout);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

29.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	348 KB	Output isn't correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Incorrect	0 ms	348 KB	Output isn't correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	536 ms	25752 KB	Output is correct
8	Incorrect	0 ms	344 KB	Output isn't 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	Incorrect	1 ms	348 KB	Output isn't correct
13	Incorrect	1 ms	348 KB	Output isn't correct
14	Incorrect	2 ms	348 KB	Output isn't correct
15	Incorrect	1 ms	348 KB	Output isn't correct
16	Correct	1 ms	348 KB	Output is correct
17	Incorrect	3 ms	348 KB	Output isn't correct
18	Correct	1 ms	348 KB	Output is correct
19	Incorrect	5 ms	348 KB	Output isn't correct
20	Correct	2 ms	348 KB	Output is correct
21	Incorrect	15 ms	344 KB	Output isn't correct
22	Correct	8 ms	348 KB	Output is correct
23	Incorrect	42 ms	540 KB	Output isn't correct
24	Correct	27 ms	348 KB	Output is correct
25	Incorrect	72 ms	348 KB	Output isn't correct
26	Correct	46 ms	348 KB	Output is correct
27	Incorrect	122 ms	600 KB	Output isn't correct
28	Correct	71 ms	604 KB	Output is correct
29	Incorrect	135 ms	620 KB	Output isn't correct
30	Correct	89 ms	620 KB	Output is correct
31	Incorrect	179 ms	600 KB	Output isn't correct
32	Correct	122 ms	604 KB	Output is correct
33	Execution timed out	1046 ms	5808 KB	Time limit exceeded
34	Execution timed out	1018 ms	5636 KB	Time limit exceeded
35	Correct	124 ms	5388 KB	Output is correct
36	Execution timed out	1045 ms	7148 KB	Time limit exceeded
37	Execution timed out	1048 ms	6928 KB	Time limit exceeded
38	Correct	185 ms	6856 KB	Output is correct
39	Execution timed out	1041 ms	8592 KB	Time limit exceeded
40	Execution timed out	1052 ms	8692 KB	Time limit exceeded
41	Correct	199 ms	8616 KB	Output is correct
42	Execution timed out	1032 ms	10560 KB	Time limit exceeded
43	Execution timed out	1054 ms	10500 KB	Time limit exceeded
44	Correct	246 ms	10476 KB	Output is correct
45	Execution timed out	1067 ms	12584 KB	Time limit exceeded
46	Execution timed out	1064 ms	12620 KB	Time limit exceeded
47	Correct	331 ms	12604 KB	Output is correct
48	Execution timed out	1006 ms	15028 KB	Time limit exceeded
49	Execution timed out	1045 ms	15084 KB	Time limit exceeded
50	Correct	458 ms	14848 KB	Output is correct
51	Execution timed out	1034 ms	17696 KB	Time limit exceeded
52	Execution timed out	1047 ms	17844 KB	Time limit exceeded
53	Correct	534 ms	17428 KB	Output is correct
54	Execution timed out	1053 ms	20268 KB	Time limit exceeded
55	Execution timed out	1028 ms	20172 KB	Time limit exceeded
56	Correct	570 ms	20084 KB	Output is correct
57	Execution timed out	1048 ms	23284 KB	Time limit exceeded
58	Execution timed out	1034 ms	23252 KB	Time limit exceeded
59	Correct	720 ms	23164 KB	Output is correct
60	Execution timed out	1012 ms	26296 KB	Time limit exceeded
61	Execution timed out	1048 ms	26132 KB	Time limit exceeded
62	Correct	836 ms	26312 KB	Output is correct
63	Incorrect	418 ms	26272 KB	Output isn't correct
64	Incorrect	725 ms	26020 KB	Output isn't correct
65	Incorrect	706 ms	26116 KB	Output isn't correct
66	Incorrect	540 ms	26212 KB	Output isn't correct
67	Incorrect	423 ms	26064 KB	Output isn't correct
68	Incorrect	191 ms	26144 KB	Output isn't correct
69	Incorrect	219 ms	26064 KB	Output isn't correct
70	Incorrect	197 ms	26184 KB	Output isn't correct
71	Incorrect	162 ms	26208 KB	Output isn't correct
72	Incorrect	123 ms	26196 KB	Output isn't correct
73	Incorrect	200 ms	26296 KB	Output isn't correct
74	Correct	350 ms	26196 KB	Output is correct
75	Correct	437 ms	26212 KB	Output is correct
76	Correct	403 ms	26148 KB	Output is correct
77	Correct	437 ms	26240 KB	Output is correct
78	Incorrect	438 ms	26192 KB	Output isn't correct
79	Correct	332 ms	26344 KB	Output is correct
80	Correct	393 ms	26124 KB	Output is correct
81	Correct	428 ms	26280 KB	Output is correct
82	Correct	359 ms	26156 KB	Output is correct
83	Correct	554 ms	26400 KB	Output is correct
84	Correct	422 ms	25980 KB	Output is correct
85	Correct	482 ms	26168 KB	Output is correct
86	Correct	528 ms	26264 KB	Output is correct
87	Correct	461 ms	26144 KB	Output is correct
88	Correct	570 ms	26148 KB	Output is correct
89	Correct	637 ms	26304 KB	Output is correct
90	Correct	564 ms	26328 KB	Output is correct
91	Correct	513 ms	26120 KB	Output is correct
92	Correct	520 ms	26440 KB	Output is correct