제출 #338590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338590		blue	Mecho (IOI09_mecho)	C++11	81 / 100	1079 ms	8812 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
*/
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;
vector<int> dist(800*800, 1e9);
//LOOKS GOOD

int INF = 1e9;

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;
    while(!tbv.empty())
    {
        u = tbv.front();
    //    cout << u << ' ' << dist[u] << '\n';
        tbv.pop();

        vector<int> 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(int 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(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;
    }

    vector<int> visit(N*N, 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, INF) << '\n';
}

• Subtask 1: 81 / 100