oj.uz

Submission #969073

# Submission time Handle Problem Language Result Execution time Memory
969073 2024-04-24T13:06:31 Z anango Mecho (IOI09_mecho) C++17
39 / 100
 799 ms 26028 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)) {
        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;
    }
    if (l>0 && !BSTA(l)) {
        l--;
    }
    if (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
39.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 503 ms 25728 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 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 Correct 2 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Incorrect 1 ms 348 KB Output isn't correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Incorrect 1 ms 348 KB Output isn't correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Incorrect 2 ms 348 KB Output isn't correct
25 Incorrect 1 ms 348 KB Output isn't correct
26 Incorrect 2 ms 348 KB Output isn't correct
27 Incorrect 3 ms 376 KB Output isn't correct
28 Incorrect 2 ms 604 KB Output isn't correct
29 Incorrect 2 ms 604 KB Output isn't correct
30 Incorrect 2 ms 604 KB Output isn't correct
31 Incorrect 2 ms 604 KB Output isn't correct
32 Incorrect 2 ms 604 KB Output isn't correct
33 Incorrect 45 ms 5272 KB Output isn't correct
34 Incorrect 69 ms 5268 KB Output isn't correct
35 Correct 109 ms 5288 KB Output is correct
36 Incorrect 64 ms 6940 KB Output isn't correct
37 Incorrect 91 ms 6764 KB Output isn't correct
38 Correct 159 ms 6800 KB Output is correct
39 Incorrect 71 ms 8280 KB Output isn't correct
40 Incorrect 124 ms 8280 KB Output isn't correct
41 Correct 183 ms 8452 KB Output is correct
42 Incorrect 94 ms 10312 KB Output isn't correct
43 Incorrect 148 ms 10172 KB Output isn't correct
44 Correct 235 ms 10412 KB Output is correct
45 Incorrect 107 ms 12364 KB Output isn't correct
46 Incorrect 177 ms 12344 KB Output isn't correct
47 Correct 328 ms 12620 KB Output is correct
48 Incorrect 128 ms 14640 KB Output isn't correct
49 Incorrect 209 ms 14616 KB Output isn't correct
50 Correct 385 ms 14624 KB Output is correct
51 Incorrect 151 ms 17092 KB Output isn't correct
52 Incorrect 249 ms 17292 KB Output isn't correct
53 Correct 428 ms 17036 KB Output is correct
54 Incorrect 184 ms 19768 KB Output isn't correct
55 Incorrect 309 ms 19760 KB Output isn't correct
56 Correct 551 ms 19912 KB Output is correct
57 Incorrect 222 ms 22588 KB Output isn't correct
58 Incorrect 355 ms 22800 KB Output isn't correct
59 Correct 612 ms 22608 KB Output is correct
60 Incorrect 260 ms 25816 KB Output isn't correct
61 Incorrect 399 ms 25640 KB Output isn't correct
62 Correct 799 ms 25864 KB Output is correct
63 Incorrect 422 ms 25704 KB Output isn't correct
64 Incorrect 734 ms 25648 KB Output isn't correct
65 Incorrect 665 ms 25652 KB Output isn't correct
66 Incorrect 527 ms 25660 KB Output isn't correct
67 Correct 423 ms 25924 KB Output is correct
68 Incorrect 204 ms 25716 KB Output isn't correct
69 Incorrect 221 ms 25676 KB Output isn't correct
70 Incorrect 189 ms 25712 KB Output isn't correct
71 Incorrect 162 ms 25728 KB Output isn't correct
72 Incorrect 134 ms 25772 KB Output isn't correct
73 Incorrect 175 ms 25812 KB Output isn't correct
74 Correct 337 ms 25772 KB Output is correct
75 Correct 411 ms 25764 KB Output is correct
76 Correct 376 ms 25772 KB Output is correct
77 Correct 379 ms 25784 KB Output is correct
78 Correct 446 ms 25756 KB Output is correct
79 Correct 323 ms 26028 KB Output is correct
80 Correct 368 ms 25740 KB Output is correct
81 Correct 386 ms 25776 KB Output is correct
82 Correct 346 ms 25700 KB Output is correct
83 Correct 519 ms 25776 KB Output is correct
84 Correct 390 ms 25760 KB Output is correct
85 Correct 415 ms 25712 KB Output is correct
86 Correct 496 ms 25776 KB Output is correct
87 Correct 435 ms 25748 KB Output is correct
88 Correct 574 ms 25724 KB Output is correct
89 Correct 528 ms 25912 KB Output is correct
90 Correct 537 ms 25732 KB Output is correct
91 Correct 496 ms 25696 KB Output is correct
92 Correct 517 ms 25932 KB Output is correct