Submission #533696

#	Time	Username	Problem	Language	Result	Execution time	Memory
533696		DanerZein	Hexagonal Territory (APIO21_hexagon)	C++14	11 / 100	1560 ms	1048576 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const ll mod=1e9+7;
const int MAX_N=8e3;
int X[8]={0,-2,-1,1,2,1,-1};
int Y[8]={0,0,1,1,0,-1,-1};
ll he[MAX_N+10][MAX_N+10];
int vis[MAX_N+10][MAX_N+10];
ll pot(ll b,ll e){
  if(e==1) return b;
  ll aux=pot(b,e/2);
  aux*=aux; aux%=mod;
  if(e%2!=0) aux=(aux*b)%mod;
  return aux;
}
void flod(int x,int y){
  vis[x][y]=2;
  queue<ii> q;
  q.push(ii(x,y));
  while(!q.empty()){
    int x=q.front().first;
    int y=q.front().second;
    q.pop(); 
    for(int i=1;i<=6;i++){
      int xk=x+X[i];
      int yk=y+Y[i];
      if(xk>=0 && yk>=0 && xk<=MAX_N && yk<=MAX_N && !vis[xk][yk]){
	vis[xk][yk]=2;
	q.push(ii(xk,yk));
      }
    }
  }
}
void height(int x,int y){
  for(int i=0;i<=MAX_N;i++) for(int j=0;j<=MAX_N;j++) he[i][j]=1e9;
  he[x][y]=0;
  queue<ii> q;
  q.push(ii(x,y));
  while(!q.empty()){
    int xi=q.front().first;
    int yi=q.front().second;
    q.pop();
    for(int i=1;i<=6;i++){
      int xk=xi+X[i];
      int yk=yi+Y[i];
      if(xk>=0 && yk>=0 && xk<=MAX_N && yk<=MAX_N && vis[xk][yk]<=1){
	if(he[xk][yk]>he[xi][yi]+1){
	  he[xk][yk]=he[xi][yi]+1;
	  q.push(ii(xk,yk));
	}
      }
    }
  }
}
int draw_territory(int N, int A, int B,
                   std::vector<int> D, std::vector<int> L) {
  memset(he,-1,sizeof he);
  memset(vis,0,sizeof vis);
  ll ans=0;
  int x=4e3,y=4e3;
  vis[x][y]=1;
  for(int i=0;i<N;i++){
    for(int j=0;j<L[i];j++){
      x+=X[D[i]];
      y+=Y[D[i]];
      vis[x][y]=1;
    }
  }
  for(int i=1;i<=6;i++){
    x=4e3; y=4e3;
    while(x>=0 && y>=0 && x<=MAX_N && y<=MAX_N){
      x+=X[i];
      y+=Y[i];
    }
    x-=X[i];
    y-=Y[i];
    if(!vis[x][y]){
      flod(x,y);
      break;
    }
  }
  x=4e3; y=4e3;
  height(x,y);
  for(int i=0;i<=MAX_N;i++){
    for(int j=0;j<=MAX_N;j++){
      if(he[i][j]!=1e9){
	ans+=A; ans%=mod;
	ans+=B*he[i][j]; ans%=mod;
      }
    }
  }
  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