oj.uz

Submission #969070

# Submission time Handle Problem Language Result Execution time Memory
969070 2024-04-24T13:04:39 Z anango Mecho (IOI09_mecho) C++17
57 / 100
 1000 ms 26484 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;
    }
    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
57.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 620 ms 25748 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 0 ms 432 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Execution timed out 1096 ms 360 KB Time limit exceeded
13 Incorrect 1 ms 360 KB Output isn't correct
14 Correct 2 ms 360 KB Output is correct
15 Correct 1 ms 356 KB Output is correct
16 Correct 1 ms 360 KB Output is correct
17 Correct 3 ms 480 KB Output is correct
18 Correct 2 ms 356 KB Output is correct
19 Correct 5 ms 352 KB Output is correct
20 Correct 2 ms 356 KB Output is correct
21 Correct 23 ms 356 KB Output is correct
22 Correct 8 ms 352 KB Output is correct
23 Correct 36 ms 528 KB Output is correct
24 Correct 23 ms 356 KB Output is correct
25 Correct 83 ms 580 KB Output is correct
26 Correct 46 ms 348 KB Output is correct
27 Correct 110 ms 600 KB Output is correct
28 Correct 66 ms 604 KB Output is correct
29 Correct 151 ms 848 KB Output is correct
30 Correct 102 ms 620 KB Output is correct
31 Correct 227 ms 604 KB Output is correct
32 Correct 121 ms 664 KB Output is correct
33 Execution timed out 1033 ms 5600 KB Time limit exceeded
34 Execution timed out 1036 ms 5424 KB Time limit exceeded
35 Correct 120 ms 5368 KB Output is correct
36 Execution timed out 1029 ms 7072 KB Time limit exceeded
37 Execution timed out 1067 ms 7092 KB Time limit exceeded
38 Correct 171 ms 6860 KB Output is correct
39 Execution timed out 1068 ms 8956 KB Time limit exceeded
40 Execution timed out 1060 ms 8648 KB Time limit exceeded
41 Correct 213 ms 8628 KB Output is correct
42 Execution timed out 1046 ms 10568 KB Time limit exceeded
43 Execution timed out 1014 ms 10608 KB Time limit exceeded
44 Correct 249 ms 10516 KB Output is correct
45 Execution timed out 1045 ms 12792 KB Time limit exceeded
46 Execution timed out 1033 ms 12832 KB Time limit exceeded
47 Correct 348 ms 12604 KB Output is correct
48 Execution timed out 1018 ms 14916 KB Time limit exceeded
49 Execution timed out 1055 ms 15116 KB Time limit exceeded
50 Correct 432 ms 14844 KB Output is correct
51 Execution timed out 1057 ms 18040 KB Time limit exceeded
52 Execution timed out 1016 ms 17416 KB Time limit exceeded
53 Correct 481 ms 17420 KB Output is correct
54 Execution timed out 1050 ms 20360 KB Time limit exceeded
55 Execution timed out 1059 ms 20240 KB Time limit exceeded
56 Correct 601 ms 20092 KB Output is correct
57 Execution timed out 1047 ms 23092 KB Time limit exceeded
58 Execution timed out 1102 ms 23388 KB Time limit exceeded
59 Correct 647 ms 22868 KB Output is correct
60 Execution timed out 1025 ms 26480 KB Time limit exceeded
61 Execution timed out 1051 ms 26344 KB Time limit exceeded
62 Correct 879 ms 26224 KB Output is correct
63 Incorrect 401 ms 26056 KB Output isn't correct
64 Incorrect 740 ms 26020 KB Output isn't correct
65 Incorrect 663 ms 26120 KB Output isn't correct
66 Incorrect 573 ms 26040 KB Output isn't correct
67 Correct 436 ms 26068 KB Output is correct
68 Incorrect 216 ms 26156 KB Output isn't correct
69 Incorrect 237 ms 26140 KB Output isn't correct
70 Incorrect 181 ms 26164 KB Output isn't correct
71 Incorrect 160 ms 26192 KB Output isn't correct
72 Incorrect 131 ms 26184 KB Output isn't correct
73 Incorrect 230 ms 26276 KB Output isn't correct
74 Correct 354 ms 26192 KB Output is correct
75 Correct 485 ms 26484 KB Output is correct
76 Correct 402 ms 26144 KB Output is correct
77 Correct 425 ms 26328 KB Output is correct
78 Correct 447 ms 26184 KB Output is correct
79 Correct 354 ms 26440 KB Output is correct
80 Correct 413 ms 26104 KB Output is correct
81 Correct 412 ms 26096 KB Output is correct
82 Correct 368 ms 26156 KB Output is correct
83 Correct 588 ms 26236 KB Output is correct
84 Correct 445 ms 26016 KB Output is correct
85 Correct 482 ms 26368 KB Output is correct
86 Correct 528 ms 26212 KB Output is correct
87 Correct 478 ms 26188 KB Output is correct
88 Correct 602 ms 26328 KB Output is correct
89 Correct 608 ms 26156 KB Output is correct
90 Correct 569 ms 26144 KB Output is correct
91 Correct 603 ms 26356 KB Output is correct
92 Correct 578 ms 26372 KB Output is correct