oj.uz

Submission #969029

# Submission time Handle Problem Language Result Execution time Memory
969029 2024-04-24T11:53:36 Z anango Mecho (IOI09_mecho) C++17
29 / 100
 1000 ms 26064 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]) {
                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 668 ms 25760 KB Output is correct
8 Incorrect 0 ms 348 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 1 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 344 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 472 KB Output is correct
21 Incorrect 16 ms 348 KB Output isn't correct
22 Correct 8 ms 504 KB Output is correct
23 Incorrect 35 ms 348 KB Output isn't correct
24 Correct 21 ms 344 KB Output is correct
25 Incorrect 74 ms 348 KB Output isn't correct
26 Correct 47 ms 564 KB Output is correct
27 Incorrect 118 ms 604 KB Output isn't correct
28 Correct 70 ms 604 KB Output is correct
29 Incorrect 158 ms 616 KB Output isn't correct
30 Correct 88 ms 604 KB Output is correct
31 Incorrect 179 ms 600 KB Output isn't correct
32 Correct 120 ms 604 KB Output is correct
33 Execution timed out 1083 ms 5548 KB Time limit exceeded
34 Execution timed out 1071 ms 5384 KB Time limit exceeded
35 Correct 122 ms 5296 KB Output is correct
36 Execution timed out 1077 ms 7088 KB Time limit exceeded
37 Execution timed out 1062 ms 6812 KB Time limit exceeded
38 Correct 201 ms 6932 KB Output is correct
39 Execution timed out 1098 ms 8508 KB Time limit exceeded
40 Execution timed out 1032 ms 8560 KB Time limit exceeded
41 Correct 201 ms 8696 KB Output is correct
42 Execution timed out 1044 ms 10664 KB Time limit exceeded
43 Execution timed out 1028 ms 10324 KB Time limit exceeded
44 Correct 257 ms 10340 KB Output is correct
45 Execution timed out 1055 ms 12588 KB Time limit exceeded
46 Execution timed out 1066 ms 12508 KB Time limit exceeded
47 Correct 347 ms 12400 KB Output is correct
48 Execution timed out 1062 ms 14868 KB Time limit exceeded
49 Execution timed out 1075 ms 14668 KB Time limit exceeded
50 Correct 414 ms 14900 KB Output is correct
51 Execution timed out 1042 ms 17128 KB Time limit exceeded
52 Execution timed out 1071 ms 17256 KB Time limit exceeded
53 Correct 492 ms 17100 KB Output is correct
54 Execution timed out 1035 ms 19920 KB Time limit exceeded
55 Execution timed out 1047 ms 19868 KB Time limit exceeded
56 Correct 599 ms 19756 KB Output is correct
57 Execution timed out 1062 ms 22684 KB Time limit exceeded
58 Execution timed out 1031 ms 22876 KB Time limit exceeded
59 Correct 688 ms 22696 KB Output is correct
60 Execution timed out 1022 ms 25644 KB Time limit exceeded
61 Execution timed out 1048 ms 25800 KB Time limit exceeded
62 Correct 827 ms 25660 KB Output is correct
63 Incorrect 403 ms 25660 KB Output isn't correct
64 Incorrect 741 ms 25836 KB Output isn't correct
65 Incorrect 686 ms 25756 KB Output isn't correct
66 Incorrect 527 ms 25652 KB Output isn't correct
67 Incorrect 410 ms 25688 KB Output isn't correct
68 Incorrect 203 ms 25700 KB Output isn't correct
69 Incorrect 235 ms 25792 KB Output isn't correct
70 Incorrect 177 ms 25740 KB Output isn't correct
71 Incorrect 165 ms 25788 KB Output isn't correct
72 Incorrect 127 ms 25828 KB Output isn't correct
73 Incorrect 210 ms 25828 KB Output isn't correct
74 Correct 368 ms 25768 KB Output is correct
75 Correct 445 ms 25944 KB Output is correct
76 Correct 422 ms 25760 KB Output is correct
77 Correct 398 ms 25784 KB Output is correct
78 Incorrect 498 ms 25788 KB Output isn't correct
79 Correct 335 ms 25772 KB Output is correct
80 Correct 416 ms 25844 KB Output is correct
81 Correct 420 ms 25720 KB Output is correct
82 Correct 379 ms 26064 KB Output is correct
83 Correct 535 ms 25764 KB Output is correct
84 Correct 411 ms 25748 KB Output is correct
85 Correct 458 ms 26004 KB Output is correct
86 Correct 519 ms 25776 KB Output is correct
87 Correct 479 ms 25728 KB Output is correct
88 Correct 558 ms 25696 KB Output is correct
89 Correct 548 ms 25696 KB Output is correct
90 Correct 585 ms 25692 KB Output is correct
91 Correct 527 ms 25800 KB Output is correct
92 Correct 522 ms 25736 KB Output is correct