oj.uz

Submission #737484

# Submission time Handle Problem Language Result Execution time Memory
737484 2023-05-07T08:34:33 Z keisuke6 Hexagonal Territory (APIO21_hexagon) C++14
11 / 100
 2000 ms 589236 KB 
#include "hexagon.h"
#include <vector>
#include <unordered_set>
#include <queue>
long long mod = 1000000007;
using namespace std;
int draw_territory(int N, int A, int B, std::vector<int> D, std::vector<int> L){
  int n = 2400;
  vector<vector<int>> G(n*n);
  int pos = 1200*n+1200;
  unordered_set<int> s;
  vector<int> C = {0,n,n+1,1,-n,-n-1,-1};
  for(int i=0;i<N;i++){
    for(int j=0;j<L[i];j++){
      pos += C[D[i]];
      s.insert(pos);
    }
  }
  for(int i=0;i<n;i++)for(int j=0;j<n;j++){
    if(i != 0) G[i*n+j].push_back((i-1)*n+j);
    if(i < n-1) G[i*n+j].emplace_back((i+1)*n+j);
    if(j != 0) G[i*n+j].emplace_back(i*n+j-1);
    if(j < n-1) G[i*n+j].emplace_back(i*n+j+1);
    if(i != 0 && j != 0) G[i*n+j].emplace_back((i-1)*n+(j-1));
    if(i < n-1 && j < n-1) G[i*n+j].emplace_back((i+1)*n+(j+1));
  }
  vector<int> dist(n*n,1e9);
  vector<bool> seen(n*n,false);
  seen[0] = true;
  dist[pos] = 0;
  queue<int> q;
  q.push(0);
  while(!q.empty()){
    int po = q.front();
    q.pop();
    for(int x:G[po]){
      if(seen[x] == true || s.count(x)) continue;
      q.push(x);
      seen[x] = true;
    }
  }
  q.push(pos);
  while(!q.empty()){
    int po = q.front();
    q.pop();
    for(int x:G[po]){
      if(dist[x] != 1e9 || seen[x]) continue;
      q.push(x);
      dist[x] = dist[po] + 1;
    }
  }
  long long ans = 0;
  for(int i=0;i<n*n;i++){
    if(seen[i]) continue;
    ans += A+(long long)(B)*dist[i];
    ans %= mod;
  } 
  return (int)((ans+mod)%mod);
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 589236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 568132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1291 ms 429236 KB Output is correct
2 Correct 1237 ms 429368 KB Output is correct
3 Correct 1241 ms 429216 KB Output is correct
4 Correct 1353 ms 429372 KB Output is correct
5 Correct 1248 ms 429428 KB Output is correct
6 Correct 1269 ms 429472 KB Output is correct
7 Correct 1323 ms 429348 KB Output is correct
8 Correct 1285 ms 429404 KB Output is correct
9 Correct 1286 ms 429276 KB Output is correct
10 Correct 1297 ms 429312 KB Output is correct
11 Correct 1338 ms 429368 KB Output is correct
12 Correct 1338 ms 429372 KB Output is correct
13 Correct 1233 ms 429304 KB Output is correct
14 Correct 1461 ms 429348 KB Output is correct
15 Correct 1292 ms 429368 KB Output is correct
16 Correct 1227 ms 429340 KB Output is correct
17 Correct 1310 ms 429304 KB Output is correct
18 Correct 1269 ms 429400 KB Output is correct
19 Correct 1255 ms 429324 KB Output is correct
20 Correct 1259 ms 429296 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1380 ms 437984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 570808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1262 ms 429192 KB Output is correct
2 Correct 1217 ms 429352 KB Output is correct
3 Correct 1274 ms 429200 KB Output is correct
4 Correct 1276 ms 429372 KB Output is correct
5 Correct 1278 ms 429452 KB Output is correct
6 Correct 1234 ms 429148 KB Output is correct
7 Correct 1290 ms 429260 KB Output is correct
8 Correct 1275 ms 429384 KB Output is correct
9 Correct 1310 ms 429380 KB Output is correct
10 Correct 1309 ms 429372 KB Output is correct
11 Correct 1291 ms 429364 KB Output is correct
12 Correct 1250 ms 429356 KB Output is correct
13 Correct 1223 ms 429196 KB Output is correct
14 Correct 1441 ms 429268 KB Output is correct
15 Correct 1350 ms 429388 KB Output is correct
16 Correct 1378 ms 429276 KB Output is correct
17 Correct 1266 ms 429284 KB Output is correct
18 Incorrect 1321 ms 437920 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2093 ms 575588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1235 ms 429168 KB Output is correct
2 Execution timed out 2090 ms 573228 KB Time limit exceeded
3 Halted 0 ms 0 KB -