Submission #969046

# Submission time Handle Problem Language Result Execution time Memory
969046 2024-04-24T12:24:41 Z anango Mecho (IOI09_mecho) C++17
0 / 100
1000 ms 26004 KB
#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
            //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[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: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);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory 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 Incorrect 0 ms 348 KB Output isn't correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Incorrect 646 ms 25804 KB Output isn't correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Incorrect 0 ms 384 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Incorrect 1 ms 348 KB Output isn't 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 Incorrect 1 ms 348 KB Output isn't correct
17 Incorrect 3 ms 348 KB Output isn't correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Incorrect 5 ms 472 KB Output isn't correct
20 Incorrect 2 ms 348 KB Output isn't correct
21 Incorrect 20 ms 500 KB Output isn't correct
22 Incorrect 8 ms 348 KB Output isn't correct
23 Incorrect 35 ms 348 KB Output isn't correct
24 Incorrect 21 ms 540 KB Output isn't correct
25 Incorrect 81 ms 348 KB Output isn't correct
26 Incorrect 46 ms 560 KB Output isn't correct
27 Incorrect 108 ms 604 KB Output isn't correct
28 Incorrect 76 ms 604 KB Output isn't correct
29 Incorrect 133 ms 604 KB Output isn't correct
30 Incorrect 90 ms 616 KB Output isn't correct
31 Incorrect 181 ms 648 KB Output isn't correct
32 Incorrect 125 ms 644 KB Output isn't correct
33 Execution timed out 1061 ms 5384 KB Time limit exceeded
34 Execution timed out 1054 ms 5376 KB Time limit exceeded
35 Incorrect 151 ms 5292 KB Output isn't correct
36 Execution timed out 1068 ms 6820 KB Time limit exceeded
37 Execution timed out 1041 ms 7132 KB Time limit exceeded
38 Incorrect 170 ms 6776 KB Output isn't correct
39 Execution timed out 1101 ms 8580 KB Time limit exceeded
40 Execution timed out 1064 ms 8620 KB Time limit exceeded
41 Incorrect 225 ms 8456 KB Output isn't correct
42 Execution timed out 1052 ms 10452 KB Time limit exceeded
43 Execution timed out 1065 ms 10356 KB Time limit exceeded
44 Incorrect 277 ms 10340 KB Output isn't correct
45 Execution timed out 1064 ms 12484 KB Time limit exceeded
46 Execution timed out 1038 ms 12440 KB Time limit exceeded
47 Incorrect 321 ms 12380 KB Output isn't correct
48 Execution timed out 1036 ms 14880 KB Time limit exceeded
49 Execution timed out 1078 ms 14844 KB Time limit exceeded
50 Incorrect 402 ms 14640 KB Output isn't correct
51 Execution timed out 1066 ms 17312 KB Time limit exceeded
52 Execution timed out 1062 ms 17368 KB Time limit exceeded
53 Incorrect 469 ms 17096 KB Output isn't correct
54 Execution timed out 1041 ms 19948 KB Time limit exceeded
55 Execution timed out 1065 ms 19756 KB Time limit exceeded
56 Incorrect 622 ms 19760 KB Output isn't correct
57 Execution timed out 1034 ms 22684 KB Time limit exceeded
58 Execution timed out 1073 ms 22620 KB Time limit exceeded
59 Incorrect 673 ms 22860 KB Output isn't correct
60 Execution timed out 1061 ms 25880 KB Time limit exceeded
61 Execution timed out 1065 ms 25740 KB Time limit exceeded
62 Incorrect 841 ms 25776 KB Output isn't correct
63 Incorrect 426 ms 25636 KB Output isn't correct
64 Incorrect 715 ms 25792 KB Output isn't correct
65 Incorrect 710 ms 25800 KB Output isn't correct
66 Incorrect 557 ms 25836 KB Output isn't correct
67 Incorrect 419 ms 25660 KB Output isn't correct
68 Incorrect 245 ms 25960 KB Output isn't correct
69 Incorrect 231 ms 25692 KB Output isn't correct
70 Incorrect 230 ms 25704 KB Output isn't correct
71 Incorrect 170 ms 25724 KB Output isn't correct
72 Incorrect 127 ms 25812 KB Output isn't correct
73 Incorrect 241 ms 25848 KB Output isn't correct
74 Incorrect 375 ms 25824 KB Output isn't correct
75 Incorrect 396 ms 25856 KB Output isn't correct
76 Incorrect 386 ms 25756 KB Output isn't correct
77 Incorrect 420 ms 26004 KB Output isn't correct
78 Incorrect 438 ms 25784 KB Output isn't correct
79 Incorrect 338 ms 25928 KB Output isn't correct
80 Incorrect 404 ms 25756 KB Output isn't correct
81 Incorrect 423 ms 25848 KB Output isn't correct
82 Incorrect 410 ms 25768 KB Output isn't correct
83 Incorrect 497 ms 25816 KB Output isn't correct
84 Incorrect 427 ms 25728 KB Output isn't correct
85 Incorrect 489 ms 25820 KB Output isn't correct
86 Incorrect 547 ms 25816 KB Output isn't correct
87 Incorrect 471 ms 25736 KB Output isn't correct
88 Incorrect 531 ms 25952 KB Output isn't correct
89 Incorrect 573 ms 25848 KB Output isn't correct
90 Incorrect 584 ms 25704 KB Output isn't correct
91 Incorrect 505 ms 25704 KB Output isn't correct
92 Incorrect 553 ms 25736 KB Output isn't correct