Submission #598326

#	Time	Username	Problem	Language	Result	Execution time	Memory
598326		Hanksburger	Mecho (IOI09_mecho)	C++17	84 / 100	353 ms	39140 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[640005], bee;
queue<pair<int, int> > qq;
char a[640005];
bool b[640005];
int d[640005];
queue<int> q;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, p, s, e, l=-1, r=1e6;
    cin >> n >> p;
    for (int i=0; i<n*n; i++)
    {
        cin >> a[i];
        if (a[i]=='M')
            s=i;
        else if (a[i]=='D')
            e=i;
        else if (a[i]=='H')
            bee.push_back(i);
        if (a[i]!='T')
        {
            a[i]='G';
            if (i>=n && a[i-n]=='G')
            {
                adj[i].push_back(i-n);
                adj[i-n].push_back(i);
            }
            if (i%n && a[i-1]=='G')
            {
                adj[i].push_back(i-1);
                adj[i-1].push_back(i);
            }
        }
    }
    for (int u:bee)
    {
        b[u]=1;
        q.push(u);
    }
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int v:adj[u])
        {
            if (!b[v] && v!=e)
            {
                d[v]=d[u]+1;
                b[v]=1;
                q.push(v);
            }
        }
    }
    while (l<r)
    {
        int m=(l+r+1)/2;
        for (int i=0; i<n*n; i++)
            b[i]=0;
        qq.push({s, 0});
        b[s]=1;
        bool ok=0;
        while (!qq.empty())
        {
            int u=qq.front().first, w=qq.front().second;
            qq.pop();
            for (int v:adj[u])
            {
                if (v==e)
                {
                    ok=1;
                    break;
                }
                if (!b[v] && w+1<(d[v]-m)*p)
                {
                    b[v]=1;
                    qq.push({v, w+1});
                }
            }
            if (ok)
                while (!qq.empty())
                    qq.pop();
        }
        if (ok)
            l=m;
        else
            r=m-1;
    }
    cout << l;
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:65:13: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |         b[s]=1;
      |         ~~~~^~
mecho.cpp:51:23: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |             if (!b[v] && v!=e)
      |                 ~~~~~~^~~~~~~

• Subtask 1: 84 / 100