oj.uz

Submission #969080

# Submission time Handle Problem Language Result Execution time Memory
969080 2024-04-24T13:14:36 Z anango Mecho (IOI09_mecho) C++17
57 / 100
 1000 ms 25976 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 || 0) 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 || 0) freopen("input.txt","r",stdin);
    if (debug || 0) 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:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     if (debug || 0) freopen("input.txt","r",stdin);
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:87:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     if (debug || 0) freopen("output.txt","w",stdout);
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
57.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 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 559 ms 25700 KB Output is correct
8 Correct 0 ms 344 KB Output is 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 Execution timed out 1095 ms 348 KB Time limit exceeded
13 Incorrect 1 ms 348 KB Output isn't correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 3 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 2 ms 348 KB Output is correct
21 Correct 15 ms 344 KB Output is correct
22 Correct 8 ms 348 KB Output is correct
23 Correct 35 ms 520 KB Output is correct
24 Correct 21 ms 348 KB Output is correct
25 Correct 74 ms 344 KB Output is correct
26 Correct 50 ms 596 KB Output is correct
27 Correct 105 ms 604 KB Output is correct
28 Correct 65 ms 600 KB Output is correct
29 Correct 134 ms 612 KB Output is correct
30 Correct 89 ms 600 KB Output is correct
31 Correct 181 ms 600 KB Output is correct
32 Correct 120 ms 604 KB Output is correct
33 Execution timed out 1055 ms 5512 KB Time limit exceeded
34 Execution timed out 1062 ms 5476 KB Time limit exceeded
35 Correct 120 ms 5312 KB Output is correct
36 Execution timed out 1046 ms 7024 KB Time limit exceeded
37 Execution timed out 1046 ms 6936 KB Time limit exceeded
38 Correct 173 ms 6800 KB Output is correct
39 Execution timed out 1012 ms 8704 KB Time limit exceeded
40 Execution timed out 1049 ms 8660 KB Time limit exceeded
41 Correct 204 ms 8276 KB Output is correct
42 Execution timed out 1061 ms 10576 KB Time limit exceeded
43 Execution timed out 1057 ms 10536 KB Time limit exceeded
44 Correct 253 ms 10324 KB Output is correct
45 Execution timed out 1076 ms 12540 KB Time limit exceeded
46 Execution timed out 1044 ms 12592 KB Time limit exceeded
47 Correct 348 ms 12608 KB Output is correct
48 Execution timed out 1029 ms 14688 KB Time limit exceeded
49 Execution timed out 1056 ms 14880 KB Time limit exceeded
50 Correct 414 ms 14644 KB Output is correct
51 Execution timed out 1022 ms 17440 KB Time limit exceeded
52 Execution timed out 1067 ms 17312 KB Time limit exceeded
53 Correct 497 ms 17104 KB Output is correct
54 Execution timed out 1053 ms 19924 KB Time limit exceeded
55 Execution timed out 1102 ms 20004 KB Time limit exceeded
56 Correct 591 ms 19844 KB Output is correct
57 Execution timed out 1067 ms 22916 KB Time limit exceeded
58 Execution timed out 1076 ms 23076 KB Time limit exceeded
59 Correct 664 ms 22616 KB Output is correct
60 Execution timed out 1049 ms 25904 KB Time limit exceeded
61 Execution timed out 1059 ms 25936 KB Time limit exceeded
62 Correct 852 ms 25952 KB Output is correct
63 Incorrect 384 ms 25636 KB Output isn't correct
64 Incorrect 736 ms 25828 KB Output isn't correct
65 Incorrect 679 ms 25648 KB Output isn't correct
66 Incorrect 571 ms 25752 KB Output isn't correct
67 Correct 466 ms 25656 KB Output is correct
68 Incorrect 207 ms 25720 KB Output isn't correct
69 Incorrect 224 ms 25676 KB Output isn't correct
70 Incorrect 207 ms 25720 KB Output isn't correct
71 Incorrect 168 ms 25752 KB Output isn't correct
72 Incorrect 124 ms 25740 KB Output isn't correct
73 Incorrect 206 ms 25856 KB Output isn't correct
74 Correct 366 ms 25956 KB Output is correct
75 Correct 443 ms 25756 KB Output is correct
76 Correct 403 ms 25768 KB Output is correct
77 Correct 431 ms 25860 KB Output is correct
78 Correct 483 ms 25780 KB Output is correct
79 Correct 350 ms 25920 KB Output is correct
80 Correct 377 ms 25724 KB Output is correct
81 Correct 419 ms 25976 KB Output is correct
82 Correct 376 ms 25780 KB Output is correct
83 Correct 599 ms 25756 KB Output is correct
84 Correct 413 ms 25732 KB Output is correct
85 Correct 457 ms 25736 KB Output is correct
86 Correct 536 ms 25848 KB Output is correct
87 Correct 473 ms 25716 KB Output is correct
88 Correct 567 ms 25964 KB Output is correct
89 Correct 557 ms 25708 KB Output is correct
90 Correct 582 ms 25692 KB Output is correct
91 Correct 543 ms 25700 KB Output is correct
92 Correct 551 ms 25748 KB Output is correct