Submission #969047

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969047	2024-04-24T12:32:45 Z	anango	Mecho (IOI09_mecho)	C++17	44 / 100	1000 ms	26248 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=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)) {
        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: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

44.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 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	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	592 ms	25700 KB	Output is correct
8	Incorrect	1 ms	348 KB	Output isn't correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	600 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Execution timed out	1051 ms	344 KB	Time limit exceeded
13	Incorrect	1 ms	348 KB	Output isn't correct
14	Incorrect	3 ms	348 KB	Output isn't correct
15	Correct	1 ms	600 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	3 ms	344 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	5 ms	400 KB	Output is correct
20	Correct	4 ms	348 KB	Output is correct
21	Correct	15 ms	348 KB	Output is correct
22	Correct	8 ms	504 KB	Output is correct
23	Correct	35 ms	348 KB	Output is correct
24	Correct	21 ms	344 KB	Output is correct
25	Correct	76 ms	348 KB	Output is correct
26	Correct	57 ms	580 KB	Output is correct
27	Correct	104 ms	600 KB	Output is correct
28	Correct	66 ms	604 KB	Output is correct
29	Correct	150 ms	604 KB	Output is correct
30	Correct	96 ms	620 KB	Output is correct
31	Correct	178 ms	604 KB	Output is correct
32	Correct	126 ms	600 KB	Output is correct
33	Execution timed out	1058 ms	5560 KB	Time limit exceeded
34	Execution timed out	1024 ms	5484 KB	Time limit exceeded
35	Correct	125 ms	5276 KB	Output is correct
36	Execution timed out	1078 ms	7180 KB	Time limit exceeded
37	Execution timed out	1066 ms	6848 KB	Time limit exceeded
38	Correct	173 ms	7012 KB	Output is correct
39	Execution timed out	1071 ms	8516 KB	Time limit exceeded
40	Execution timed out	1065 ms	8456 KB	Time limit exceeded
41	Correct	209 ms	8276 KB	Output is correct
42	Execution timed out	1029 ms	10384 KB	Time limit exceeded
43	Execution timed out	1051 ms	10440 KB	Time limit exceeded
44	Correct	258 ms	10332 KB	Output is correct
45	Execution timed out	1036 ms	12808 KB	Time limit exceeded
46	Execution timed out	1029 ms	12556 KB	Time limit exceeded
47	Correct	341 ms	12372 KB	Output is correct
48	Execution timed out	1048 ms	15124 KB	Time limit exceeded
49	Execution timed out	1063 ms	14840 KB	Time limit exceeded
50	Correct	447 ms	14840 KB	Output is correct
51	Execution timed out	1065 ms	17380 KB	Time limit exceeded
52	Execution timed out	1035 ms	17164 KB	Time limit exceeded
53	Correct	469 ms	17132 KB	Output is correct
54	Execution timed out	1069 ms	20052 KB	Time limit exceeded
55	Execution timed out	1053 ms	19772 KB	Time limit exceeded
56	Correct	644 ms	19768 KB	Output is correct
57	Execution timed out	1056 ms	22940 KB	Time limit exceeded
58	Execution timed out	1022 ms	22664 KB	Time limit exceeded
59	Correct	639 ms	22608 KB	Output is correct
60	Execution timed out	1049 ms	25776 KB	Time limit exceeded
61	Execution timed out	1069 ms	25792 KB	Time limit exceeded
62	Correct	835 ms	25664 KB	Output is correct
63	Incorrect	412 ms	25640 KB	Output isn't correct
64	Incorrect	752 ms	25684 KB	Output isn't correct
65	Incorrect	687 ms	25792 KB	Output isn't correct
66	Incorrect	548 ms	25676 KB	Output isn't correct
67	Incorrect	458 ms	25660 KB	Output isn't correct
68	Incorrect	210 ms	25824 KB	Output isn't correct
69	Incorrect	216 ms	25684 KB	Output isn't correct
70	Incorrect	177 ms	25768 KB	Output isn't correct
71	Incorrect	173 ms	25772 KB	Output isn't correct
72	Incorrect	137 ms	25908 KB	Output isn't correct
73	Incorrect	205 ms	25844 KB	Output isn't correct
74	Correct	377 ms	26248 KB	Output is correct
75	Correct	461 ms	25752 KB	Output is correct
76	Correct	437 ms	25764 KB	Output is correct
77	Correct	445 ms	25728 KB	Output is correct
78	Incorrect	525 ms	25748 KB	Output isn't correct
79	Correct	360 ms	25936 KB	Output is correct
80	Correct	377 ms	25772 KB	Output is correct
81	Correct	420 ms	25888 KB	Output is correct
82	Correct	357 ms	25756 KB	Output is correct
83	Correct	607 ms	25880 KB	Output is correct
84	Correct	438 ms	26032 KB	Output is correct
85	Correct	473 ms	25732 KB	Output is correct
86	Correct	575 ms	25828 KB	Output is correct
87	Correct	487 ms	25948 KB	Output is correct
88	Correct	648 ms	25724 KB	Output is correct
89	Correct	609 ms	25696 KB	Output is correct
90	Correct	576 ms	26008 KB	Output is correct
91	Correct	565 ms	26008 KB	Output is correct
92	Correct	520 ms	25700 KB	Output is correct