Submission #338583

#	Time	Username	Problem	Language	Result	Execution time	Memory
338583		blue	Mecho (IOI09_mecho)	C++11	44 / 100	485 ms	65540 KiB

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
*/
long long N, S;
long long grid[800*800]; //the number of minutes before this location cannot be occupied anymore.
long long mecho;
long long home;
//LOOKS GOOD

long long INF = 2e9;

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

    vector<long long> dist(N*N, INF);
    //cout << mecho << ' ' << dist[mecho] << ' ' << home << '\n';

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


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

        vector<long long> edge; //check down
        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(long long v: edge)
        {
            if(dist[v] != INF) continue;
            if(dist[u] + 1 >= grid[v]) continue;
            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()
{
    char c;
    cin >> N >> S;

    for(long long 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;
    }

    vector<long long> visit(N*N, 0);

    queue<long long> tbv;

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

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

        vector<long long> edge;
        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(long long v: edge)
        {
            if(visit[v]) continue;
            if(grid[v] > grid[u] + S)
            {
                grid[v] = grid[u] + S;
                tbv.push(v);
            }
        }
    }

    grid[home] = INF;

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

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

• Subtask 1: 44 / 100