oj.uz

Submission #547363

# Submission time Handle Problem Language Result Execution time Memory
547363 2022-04-10T14:11:34 Z pancankes Mecho (IOI09_mecho) C++17
38 / 100
 214 ms 12236 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
using namespace std;
#define int long long
const int INF=1e18;
const int MAXN=801;

int n,s,ans=0;
string grid[MAXN];
int bee[MAXN][MAXN],dist[MAXN][MAXN];
vector<pair<int,int>> hives;
pair<int,int> start,dest;

int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
bool inside(int x, int y) {
	return (x > -1 && x < n && y > -1 && y < n && grid[x][y] != 'T');
}

void setIO(string name="") { 
    ios_base::sync_with_stdio(0); cin.tie(0); 
    if (!name.empty()) {
        freopen((name+".in").c_str(), "r", stdin); 
        freopen((name+".out").c_str(), "w", stdout);
    }
}

// check if after eating for t seconds,
// is it possible to reach the destination
bool check(int t)
{
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            dist[i][j]=INF;
    queue<pair<int,int>>q;
    q.push(start);
    dist[start.first][start.second]=0;
    while (!q.empty())
    {
        pair<int,int> c=q.front();
        q.pop();

        for (int i=0; i<4; i++)
        {
            int x=c.first+dx[i],y=c.second+dy[i];
            // if i can usually get there in 7 step
            // taking 2 steps a minute i can get there in ceil(7/2) steps
            if (inside(x,y)&&dist[x][y]==INF&&(bee[x][y]-t)>=ceil((double)(dist[c.first][c.second]+1)/(double)s))
            {
                dist[x][y]=dist[c.first][c.second]+1;
                q.push({x,y});
            }
        }
    }
    // cout << t << endl;
    // for (int i=0; i<n; i++) {for (int j=0; j<n; j++) cout << dist[i][j] << " "; cout << endl;}
    if (dist[dest.first][dest.second]!=INF) return true;
    else return false;
}

int32_t main()
{
    cin >> n >> s;
    for (int i=0; i<n; i++) cin >> grid[i];
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        {
            if (grid[i][j]=='M') start={i,j};
            if (grid[i][j]=='D') dest={i,j};
            if (grid[i][j]=='H') hives.push_back({i,j});
            bee[i][j]=INF;
        }
    // multisource bfs to find the distances of cells from hive
    queue<pair<int,int>> q;
    for (int i=0; i<hives.size(); i++) {
        q.push(hives[i]);
        bee[hives[i].first][hives[i].second]=0;
    }
    while (!q.empty())
    {
        pair<int,int> c=q.front();
        q.pop();
        for (int i=0; i<4; i++)
        {
            int x=c.first+dx[i],y=c.second+dy[i];
            if (inside(x,y)&&grid[x][y]!='D'&&bee[x][y]==INF)
            {
                bee[x][y]=bee[c.first][c.second]+1;
                q.push({x,y});
            }
        }
    }
    // for (int i=0; i<n; i++) {for (int j=0; j<n; j++) cout << bee[i][j] << " "; cout << endl;} cout << endl;
    int lo=0,hi=2000;
    while (lo<=hi)
    {
        int mid=lo+(hi-lo)/2;
        // cout << mid << endl;
        if (check(mid))
        {
            ans=max(ans,mid);
            lo=mid+1;
        }
        else hi=mid-1;
    }
    if (!check(0)) cout << -1 << endl;
    else cout << ans << endl;
}

Compilation message

mecho.cpp: In function 'int32_t main()':
mecho.cpp:79:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i=0; i<hives.size(); i++) {
      |                   ~^~~~~~~~~~~~~
mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen((name+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 115 ms 11788 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 1 ms 848 KB Output isn't correct
13 Incorrect 1 ms 724 KB Output isn't correct
14 Correct 1 ms 852 KB Output is correct
15 Incorrect 1 ms 468 KB Output isn't correct
16 Correct 1 ms 468 KB Output is correct
17 Incorrect 1 ms 464 KB Output isn't correct
18 Correct 1 ms 468 KB Output is correct
19 Incorrect 1 ms 596 KB Output isn't correct
20 Correct 1 ms 596 KB Output is correct
21 Incorrect 1 ms 596 KB Output isn't correct
22 Correct 1 ms 596 KB Output is correct
23 Incorrect 1 ms 724 KB Output isn't correct
24 Correct 1 ms 724 KB Output is correct
25 Incorrect 1 ms 852 KB Output isn't correct
26 Correct 1 ms 848 KB Output is correct
27 Incorrect 1 ms 852 KB Output isn't correct
28 Correct 1 ms 848 KB Output is correct
29 Incorrect 1 ms 980 KB Output isn't correct
30 Correct 1 ms 980 KB Output is correct
31 Incorrect 1 ms 980 KB Output isn't correct
32 Correct 1 ms 980 KB Output is correct
33 Incorrect 19 ms 4992 KB Output isn't correct
34 Incorrect 23 ms 5004 KB Output isn't correct
35 Correct 26 ms 5012 KB Output is correct
36 Incorrect 23 ms 5692 KB Output isn't correct
37 Incorrect 29 ms 5588 KB Output isn't correct
38 Correct 33 ms 5600 KB Output is correct
39 Incorrect 31 ms 6280 KB Output isn't correct
40 Incorrect 36 ms 6360 KB Output isn't correct
41 Correct 43 ms 6356 KB Output is correct
42 Incorrect 37 ms 7252 KB Output isn't correct
43 Incorrect 50 ms 7252 KB Output isn't correct
44 Correct 54 ms 7232 KB Output is correct
45 Incorrect 43 ms 8032 KB Output isn't correct
46 Incorrect 64 ms 8140 KB Output isn't correct
47 Correct 81 ms 8048 KB Output is correct
48 Incorrect 56 ms 8768 KB Output isn't correct
49 Incorrect 63 ms 8660 KB Output isn't correct
50 Correct 82 ms 8772 KB Output is correct
51 Incorrect 61 ms 9508 KB Output isn't correct
52 Incorrect 75 ms 9428 KB Output isn't correct
53 Correct 100 ms 9420 KB Output is correct
54 Incorrect 70 ms 10240 KB Output isn't correct
55 Incorrect 83 ms 10188 KB Output isn't correct
56 Correct 118 ms 10252 KB Output is correct
57 Incorrect 81 ms 10916 KB Output isn't correct
58 Incorrect 96 ms 10964 KB Output isn't correct
59 Correct 139 ms 10968 KB Output is correct
60 Incorrect 91 ms 11636 KB Output isn't correct
61 Incorrect 114 ms 11632 KB Output isn't correct
62 Correct 160 ms 11648 KB Output is correct
63 Correct 136 ms 11596 KB Output is correct
64 Correct 214 ms 11680 KB Output is correct
65 Correct 192 ms 11632 KB Output is correct
66 Incorrect 168 ms 11572 KB Output isn't correct
67 Correct 130 ms 11664 KB Output is correct
68 Correct 77 ms 11704 KB Output is correct
69 Correct 72 ms 11712 KB Output is correct
70 Correct 59 ms 11684 KB Output is correct
71 Correct 53 ms 11724 KB Output is correct
72 Incorrect 59 ms 11708 KB Output isn't correct
73 Incorrect 51 ms 12236 KB Output isn't correct
74 Correct 110 ms 12188 KB Output is correct
75 Correct 89 ms 12216 KB Output is correct
76 Correct 83 ms 12232 KB Output is correct
77 Correct 99 ms 12216 KB Output is correct
78 Correct 87 ms 12160 KB Output is correct
79 Correct 90 ms 12108 KB Output is correct
80 Correct 80 ms 12172 KB Output is correct
81 Correct 87 ms 12148 KB Output is correct
82 Correct 83 ms 12160 KB Output is correct
83 Correct 98 ms 12080 KB Output is correct
84 Correct 106 ms 12128 KB Output is correct
85 Correct 91 ms 11980 KB Output is correct
86 Correct 100 ms 12076 KB Output is correct
87 Correct 94 ms 12060 KB Output is correct
88 Correct 98 ms 11980 KB Output is correct
89 Correct 114 ms 12032 KB Output is correct
90 Correct 105 ms 11892 KB Output is correct
91 Correct 110 ms 11972 KB Output is correct
92 Correct 101 ms 11956 KB Output is correct