Submission #338606

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338606	2020-12-23T13:24:48 Z	blue	Mecho (IOI09_mecho)	C++11	Compilation error	0 ms	0 KB

mecho

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

/*
Mecho takes at most S steps per minute.
Bees spread every minute.

(*) Restatement:
Mecho takes at most 1 step every minute.
Bees spread at the end of every S'th minute.

For every location, compute the number of minutes before the location cannot be occupied anymore.
For trees and hives this number is zero.
Consider hives as -1
Consider
*/
int N, S;
int grid[800*800]; //the number of minutes before this location cannot be occupied anymore.
int mecho;
int home;
vector<int> edge;
int dist[800*800];
//LOOKS GOOD

int INF = 2e9;

int binary_search(int a, int b)
{
    // cout << "____________________________\n binary search " << a << ' ' << b << '\n';
    int m = (a+b)/2+1;
    if(a == b) m = a;

    //cout << mecho << ' ' << dist[mecho] << ' ' << home << '\n';
    for(int i = 0; i < N*N; i++) dist[i] = INF;

    queue<int> tbv;
    dist[mecho] = m;
    tbv.push(mecho);


    int u, v;
    while(!tbv.empty())
    {
        u = tbv.front();
    //    cout << u << ' ' << dist[u] << '\n';
        tbv.pop();

        vector<int> edge; //check down
        edge.clear();
        if(u % N != 0) 
        {
            v = u-1;
            if(dist[v] == INF && dist[u] + 1 < grid[v]
            {
                dist[v] = dist[u] + 1;
                tbv.push(v);
            }
        }
        if(u % N != N-1) 
        {
            v = u+1;
            if(dist[v] == INF && dist[u] + 1 < grid[v]
            {
                dist[v] = dist[u] + 1;
                tbv.push(v);
            }
        }
        if(u >= N) 
        {
            v = u-N;
            if(dist[v] == INF && dist[u] + 1 < grid[v]
            {
                dist[v] = dist[u] + 1;
                tbv.push(v);
            }
        }
        if(u < N*(N+1)) 
        {
            v = u+N;
            if(dist[v] == INF && dist[u] + 1 < grid[v]
            {
                dist[v] = dist[u] + 1;
                tbv.push(v);
            }
        }
        
    }

    if(a == b)
    {
        if(dist[home] == INF) return -1;
        else return a/S;
    }
    else
    {
        if(dist[home] == INF) return binary_search(a, m-1);
        else return binary_search(m, b);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    char c;
    cin >> N >> S;

    for(int i = 0; i < N*N; i++)
    {
        cin >> c;
        if(c == 'T') grid[i] = 0;
        else if(c == 'G') grid[i] = INF;
        else if(c == 'M')
        {
            grid[i] = INF;
            mecho = i;
        }
        else if(c == 'D')
        {
            grid[i] = 0;
            home = i;
        }
        else grid[i] = -1;
    }

    int visit[N*N];
    for(int i = 0; i < N*N; i++) visit[i] = 0;

    queue<int> tbv;

    for(int i = 0; i < N*N; i++)
    {
        if(grid[i] != -1) continue;
        grid[i] = 0;
        tbv.push(i);
        visit[i] = 1;
    }

    while(tbv.size() > 0)
    {
        int u = tbv.front();
        tbv.pop();

        edge.clear();
        if(u % N > 0) edge.push_back(u-1);
        if(u % N < N-1) edge.push_back(u+1);
        if(u >= N) edge.push_back(u-N);
        if(u < N*(N-1)) edge.push_back(u+N);

        for(int v: edge)
        {
            if(visit[v]) continue;
            if(grid[v] > grid[u] + S)
            {
                grid[v] = grid[u] + S;
                tbv.push(v);
            }
        }
    }

    grid[home] = INF;

    // for(int i = 0; i < N*N; i++)
    // {
    //     cout << grid[i] << ' ';
    //     if(i % N == N-1) cout << '\n';
    // }

    cout << binary_search(0, 2e9) << '\n';
}

Compilation message

mecho.cpp: In function 'int binary_search(int, int)':
mecho.cpp:56:55: error: expected ')' before '{' token
   56 |             if(dist[v] == INF && dist[u] + 1 < grid[v]
      |               ~                                       ^
      |                                                       )
   57 |             {
      |             ~                                          
mecho.cpp:61:9: error: expected primary-expression before '}' token
   61 |         }
      |         ^
mecho.cpp:65:55: error: expected ')' before '{' token
   65 |             if(dist[v] == INF && dist[u] + 1 < grid[v]
      |               ~                                       ^
      |                                                       )
   66 |             {
      |             ~                                          
mecho.cpp:70:9: error: expected primary-expression before '}' token
   70 |         }
      |         ^
mecho.cpp:74:55: error: expected ')' before '{' token
   74 |             if(dist[v] == INF && dist[u] + 1 < grid[v]
      |               ~                                       ^
      |                                                       )
   75 |             {
      |             ~                                          
mecho.cpp:79:9: error: expected primary-expression before '}' token
   79 |         }
      |         ^
mecho.cpp:83:55: error: expected ')' before '{' token
   83 |             if(dist[v] == INF && dist[u] + 1 < grid[v]
      |               ~                                       ^
      |                                                       )
   84 |             {
      |             ~                                          
mecho.cpp:88:9: error: expected primary-expression before '}' token
   88 |         }
      |         ^