Submission #555483

#	Time	Username	Problem	Language	Result	Execution time	Memory
555483		joelau	Hexagonal Territory (APIO21_hexagon)	C++14	11 / 100	258 ms	143828 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;

long long dx[] = {-1,0,1,1,0,-1}, dy[] = {1,1,0,-1,-1,0}, m = 1000000007, dist[2005][2005], ufds[4500005], rnk[4500005];
bitset<2005> bs[2005];
queue< pair<long long,long long> > q;

long long findSet(long long i) {
    return ufds[i] == i ? i : ufds[i] = findSet(ufds[i]);
}

void unionSet(long long i, long long j) {
    long long a = findSet(i), b = findSet(j);
    if (a == b) return;
    if (rnk[a] < rnk[b]) ufds[a] = b;
    if (rnk[a] > rnk[b]) ufds[b] = a;
    if (rnk[a] == rnk[b]) ufds[a] = b, rnk[b]++;
}

int draw_territory(int N, int A, int B, vector<int> D, vector<int> L) {
    for (long long i = 0; i <= 4500000; ++i) ufds[i] = i, rnk[i] = 1;
    long long x = 1000, y = 1000;
    for (long long i = 0; i < N; ++i) {
        D[i]--;
        for (long long j = 0; j < L[i]; ++j) x += dx[D[i]], y += dy[D[i]], bs[x][y] = 1;
    }
    for (long long i = 0; i <= 2000; ++i) for (long long j = 0; j <= 2000; ++j) for (long long k = 0; k < 6; ++k) {
        long long x = i + dx[k], y = j + dy[k];
        if (x >= 0 && x <= 2000 && y >= 0 && y <= 2000 && bs[i][j] == bs[x][y]) unionSet(i*2001+j,x*2001+y);
    }
    memset(dist,-1,sizeof(dist));
    dist[1000][1000] = 0;
    q.emplace(1000,1000);
    long long ans = A;
    while (!q.empty()) {
        long long x,y; tie(x,y) = q.front(); q.pop();
        for (long long k = 0; k < 6; ++k) {
            long long nx = x + dx[k], ny = y + dy[k];
            if (nx >= 0 && nx <= 2000 && ny >= 0 && ny <= 2000 && dist[nx][ny] == -1 && findSet(nx*2001+ny) != findSet(0)) {
                dist[nx][ny] = dist[x][y] + 1;
                q.emplace(nx,ny);
                ans = (ans + A + dist[nx][ny] * B) % m;
            }
        }
    }
    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