oj.uz

Submission #969045

# Submission time Handle Problem Language Result Execution time Memory
969045 2024-04-24T12:22:17 Z anango Mecho (IOI09_mecho) C++17
29 / 100
 1000 ms 26440 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
            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:85:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     if (debug) freopen("input.txt","r",stdin);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
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("output.txt","w",stdout);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
29.0 / 100.0

# 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 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 536 ms 25752 KB Output is correct
8 Incorrect 0 ms 344 KB Output isn't 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 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 Correct 1 ms 348 KB Output is correct
17 Incorrect 3 ms 348 KB Output isn't correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 5 ms 348 KB Output isn't correct
20 Correct 2 ms 348 KB Output is correct
21 Incorrect 15 ms 344 KB Output isn't correct
22 Correct 8 ms 348 KB Output is correct
23 Incorrect 42 ms 540 KB Output isn't correct
24 Correct 27 ms 348 KB Output is correct
25 Incorrect 72 ms 348 KB Output isn't correct
26 Correct 46 ms 348 KB Output is correct
27 Incorrect 122 ms 600 KB Output isn't correct
28 Correct 71 ms 604 KB Output is correct
29 Incorrect 135 ms 620 KB Output isn't correct
30 Correct 89 ms 620 KB Output is correct
31 Incorrect 179 ms 600 KB Output isn't correct
32 Correct 122 ms 604 KB Output is correct
33 Execution timed out 1046 ms 5808 KB Time limit exceeded
34 Execution timed out 1018 ms 5636 KB Time limit exceeded
35 Correct 124 ms 5388 KB Output is correct
36 Execution timed out 1045 ms 7148 KB Time limit exceeded
37 Execution timed out 1048 ms 6928 KB Time limit exceeded
38 Correct 185 ms 6856 KB Output is correct
39 Execution timed out 1041 ms 8592 KB Time limit exceeded
40 Execution timed out 1052 ms 8692 KB Time limit exceeded
41 Correct 199 ms 8616 KB Output is correct
42 Execution timed out 1032 ms 10560 KB Time limit exceeded
43 Execution timed out 1054 ms 10500 KB Time limit exceeded
44 Correct 246 ms 10476 KB Output is correct
45 Execution timed out 1067 ms 12584 KB Time limit exceeded
46 Execution timed out 1064 ms 12620 KB Time limit exceeded
47 Correct 331 ms 12604 KB Output is correct
48 Execution timed out 1006 ms 15028 KB Time limit exceeded
49 Execution timed out 1045 ms 15084 KB Time limit exceeded
50 Correct 458 ms 14848 KB Output is correct
51 Execution timed out 1034 ms 17696 KB Time limit exceeded
52 Execution timed out 1047 ms 17844 KB Time limit exceeded
53 Correct 534 ms 17428 KB Output is correct
54 Execution timed out 1053 ms 20268 KB Time limit exceeded
55 Execution timed out 1028 ms 20172 KB Time limit exceeded
56 Correct 570 ms 20084 KB Output is correct
57 Execution timed out 1048 ms 23284 KB Time limit exceeded
58 Execution timed out 1034 ms 23252 KB Time limit exceeded
59 Correct 720 ms 23164 KB Output is correct
60 Execution timed out 1012 ms 26296 KB Time limit exceeded
61 Execution timed out 1048 ms 26132 KB Time limit exceeded
62 Correct 836 ms 26312 KB Output is correct
63 Incorrect 418 ms 26272 KB Output isn't correct
64 Incorrect 725 ms 26020 KB Output isn't correct
65 Incorrect 706 ms 26116 KB Output isn't correct
66 Incorrect 540 ms 26212 KB Output isn't correct
67 Incorrect 423 ms 26064 KB Output isn't correct
68 Incorrect 191 ms 26144 KB Output isn't correct
69 Incorrect 219 ms 26064 KB Output isn't correct
70 Incorrect 197 ms 26184 KB Output isn't correct
71 Incorrect 162 ms 26208 KB Output isn't correct
72 Incorrect 123 ms 26196 KB Output isn't correct
73 Incorrect 200 ms 26296 KB Output isn't correct
74 Correct 350 ms 26196 KB Output is correct
75 Correct 437 ms 26212 KB Output is correct
76 Correct 403 ms 26148 KB Output is correct
77 Correct 437 ms 26240 KB Output is correct
78 Incorrect 438 ms 26192 KB Output isn't correct
79 Correct 332 ms 26344 KB Output is correct
80 Correct 393 ms 26124 KB Output is correct
81 Correct 428 ms 26280 KB Output is correct
82 Correct 359 ms 26156 KB Output is correct
83 Correct 554 ms 26400 KB Output is correct
84 Correct 422 ms 25980 KB Output is correct
85 Correct 482 ms 26168 KB Output is correct
86 Correct 528 ms 26264 KB Output is correct
87 Correct 461 ms 26144 KB Output is correct
88 Correct 570 ms 26148 KB Output is correct
89 Correct 637 ms 26304 KB Output is correct
90 Correct 564 ms 26328 KB Output is correct
91 Correct 513 ms 26120 KB Output is correct
92 Correct 520 ms 26440 KB Output is correct