oj.uz

Submission #969025

# Submission time Handle Problem Language Result Execution time Memory
969025 2024-04-24T11:49:06 Z anango Mecho (IOI09_mecho) C++17
20 / 100
 746 ms 26396 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 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
            //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);
        }
    }
    //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++) {
            //cout << distance[i][j] <<" ";
        }
        //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() {
    //freopen("input.txt","r",stdin);
    //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;
        ////cout << st << endl;
        for (int j=0; j<n; j++) {
            ////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;
            ////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);
        }
    }
    //cout << "DISTS"<< endl;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            //cout << dist[i][j] <<" ";
        }
        //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;
    }
    cout << l-1 << endl;

}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 411 ms 25856 KB Output is correct
8 Incorrect 0 ms 344 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 432 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 0 ms 432 KB Output isn't correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Incorrect 0 ms 436 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 1 ms 348 KB Output isn't correct
25 Incorrect 1 ms 348 KB Output isn't correct
26 Incorrect 2 ms 344 KB Output isn't correct
27 Incorrect 1 ms 604 KB Output isn't correct
28 Incorrect 2 ms 616 KB Output isn't correct
29 Incorrect 1 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 37 ms 5368 KB Output isn't correct
34 Incorrect 56 ms 5392 KB Output isn't correct
35 Correct 88 ms 5380 KB Output is correct
36 Incorrect 48 ms 6876 KB Output isn't correct
37 Incorrect 75 ms 6844 KB Output isn't correct
38 Correct 127 ms 6856 KB Output is correct
39 Incorrect 68 ms 8584 KB Output isn't correct
40 Incorrect 94 ms 8580 KB Output isn't correct
41 Correct 145 ms 8624 KB Output is correct
42 Incorrect 74 ms 10496 KB Output isn't correct
43 Incorrect 123 ms 10596 KB Output isn't correct
44 Correct 185 ms 10380 KB Output is correct
45 Incorrect 90 ms 12548 KB Output isn't correct
46 Incorrect 163 ms 12588 KB Output isn't correct
47 Correct 247 ms 12604 KB Output is correct
48 Incorrect 107 ms 14888 KB Output isn't correct
49 Incorrect 179 ms 14856 KB Output isn't correct
50 Correct 305 ms 14788 KB Output is correct
51 Incorrect 126 ms 17360 KB Output isn't correct
52 Incorrect 210 ms 17732 KB Output isn't correct
53 Correct 359 ms 17380 KB Output is correct
54 Incorrect 169 ms 20040 KB Output isn't correct
55 Incorrect 259 ms 20080 KB Output isn't correct
56 Correct 440 ms 20064 KB Output is correct
57 Incorrect 222 ms 22948 KB Output isn't correct
58 Incorrect 292 ms 22936 KB Output isn't correct
59 Correct 516 ms 23092 KB Output is correct
60 Incorrect 208 ms 26064 KB Output isn't correct
61 Incorrect 344 ms 26116 KB Output isn't correct
62 Correct 660 ms 26376 KB Output is correct
63 Incorrect 386 ms 26064 KB Output isn't correct
64 Incorrect 746 ms 26040 KB Output isn't correct
65 Incorrect 656 ms 26088 KB Output isn't correct
66 Incorrect 558 ms 26140 KB Output isn't correct
67 Incorrect 418 ms 26056 KB Output isn't correct
68 Incorrect 194 ms 26144 KB Output isn't correct
69 Incorrect 216 ms 26116 KB Output isn't correct
70 Incorrect 221 ms 26180 KB Output isn't correct
71 Incorrect 160 ms 26164 KB Output isn't correct
72 Incorrect 113 ms 26200 KB Output isn't correct
73 Incorrect 162 ms 26248 KB Output isn't correct
74 Correct 278 ms 26180 KB Output is correct
75 Correct 346 ms 26216 KB Output is correct
76 Correct 324 ms 26168 KB Output is correct
77 Correct 327 ms 26240 KB Output is correct
78 Incorrect 428 ms 26136 KB Output isn't correct
79 Correct 327 ms 26224 KB Output is correct
80 Correct 300 ms 26104 KB Output is correct
81 Correct 327 ms 26148 KB Output is correct
82 Correct 287 ms 26084 KB Output is correct
83 Correct 420 ms 26396 KB Output is correct
84 Correct 335 ms 26016 KB Output is correct
85 Correct 351 ms 26248 KB Output is correct
86 Correct 387 ms 26152 KB Output is correct
87 Correct 366 ms 26164 KB Output is correct
88 Correct 408 ms 26140 KB Output is correct
89 Correct 556 ms 26336 KB Output is correct
90 Correct 443 ms 26224 KB Output is correct
91 Correct 382 ms 26104 KB Output is correct
92 Correct 411 ms 26388 KB Output is correct