Submission #824534

#	Time	Username	Problem	Language	Result	Execution time	Memory
824534		Hanksburger	Hexagonal Territory (APIO21_hexagon)	C++17	11 / 100	177 ms	159872 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
const pair<long long, long long> dir[7]={{0, 0}, {1, 0}, {0, 1}, {-1, 1}, {-1, 0}, {0, -1}, {1, -1}};
const long long mod=1000000007;
long long border[2005][2005], outside[2005][2005], dist[2005][2005];
queue<pair<long long, long long> > q;
vector<long long> d, l;
int draw_territory(int nn, int aa, int bb, vector<int> dd, vector<int> ll)
{
    long long n=nn, a=aa, b=bb, curX=1000, curY=1000, ans=0;
    for (long long i=0; i<n; i++)
        d.push_back(dd[i]), l.push_back(ll[i]);
    for (long long i=0; i<n; i++)
    {
        for (long long j=0; j<l[i]; j++)
        {
            curX+=dir[d[i]].first;
            curY+=dir[d[i]].second;
            border[curX][curY]=1;
        }
    }
    outside[2000][2000]=1;
    q.push({2000, 2000});
    while (!q.empty())
    {
        long long ux=q.front().first, uy=q.front().second;
        q.pop();
        for (long long i=1; i<=6; i++)
        {
            long long vx=ux+dir[i].first, vy=uy+dir[i].second;
            if (0<=vx && vx<=2000 && 0<=vy && vy<=2000 && !border[vx][vy] && !outside[vx][vy])
            {
                outside[vx][vy]=1;
                q.push({vx, vy});
            }
        }
    }
    for (long long i=0; i<=2000; i++)
        for (long long j=0; j<=2000; j++)
            dist[i][j]=1e9;
    dist[1000][1000]=0;
    q.push({1000, 1000});
    while (!q.empty())
    {
        long long ux=q.front().first, uy=q.front().second;
        q.pop();
        ans=(ans+a+dist[ux][uy]*b)%mod;
        for (long long i=1; i<=6; i++)
        {
            long long vx=ux+dir[i].first, vy=uy+dir[i].second;
            if (!outside[vx][vy] && dist[ux][uy]+1<dist[vx][vy])
            {
                dist[vx][vy]=dist[ux][uy]+1;
                q.push({vx, vy});
            }
        }
    }
    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16