oj.uz

Submission #555483

# Submission time Handle Problem Language Result Execution time Memory
555483 2022-05-01T04:53:56 Z joelau Hexagonal Territory (APIO21_hexagon) C++14
11 / 100
 258 ms 143828 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 143176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 143180 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 102104 KB Output is correct
2 Correct 208 ms 102192 KB Output is correct
3 Correct 220 ms 102184 KB Output is correct
4 Correct 237 ms 102164 KB Output is correct
5 Correct 251 ms 102208 KB Output is correct
6 Correct 209 ms 102164 KB Output is correct
7 Correct 215 ms 102176 KB Output is correct
8 Correct 238 ms 102152 KB Output is correct
9 Correct 212 ms 102220 KB Output is correct
10 Correct 217 ms 102132 KB Output is correct
11 Correct 218 ms 102168 KB Output is correct
12 Correct 221 ms 102240 KB Output is correct
13 Correct 223 ms 102248 KB Output is correct
14 Correct 224 ms 102364 KB Output is correct
15 Correct 212 ms 102188 KB Output is correct
16 Correct 230 ms 102188 KB Output is correct
17 Correct 222 ms 102136 KB Output is correct
18 Correct 258 ms 102380 KB Output is correct
19 Correct 209 ms 102348 KB Output is correct
20 Correct 215 ms 102228 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 87 ms 143800 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 143184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 102148 KB Output is correct
2 Correct 212 ms 102220 KB Output is correct
3 Correct 223 ms 102184 KB Output is correct
4 Correct 220 ms 102160 KB Output is correct
5 Correct 208 ms 102332 KB Output is correct
6 Correct 212 ms 102164 KB Output is correct
7 Correct 218 ms 102176 KB Output is correct
8 Correct 233 ms 102152 KB Output is correct
9 Correct 210 ms 102164 KB Output is correct
10 Correct 209 ms 102192 KB Output is correct
11 Correct 206 ms 102144 KB Output is correct
12 Correct 250 ms 102244 KB Output is correct
13 Correct 210 ms 102252 KB Output is correct
14 Correct 216 ms 102244 KB Output is correct
15 Correct 224 ms 102180 KB Output is correct
16 Correct 235 ms 102148 KB Output is correct
17 Correct 203 ms 102220 KB Output is correct
18 Runtime error 87 ms 143828 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 143252 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 102120 KB Output is correct
2 Runtime error 90 ms 143172 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -