oj.uz

Submission #316313

# Submission time Handle Problem Language Result Execution time Memory
316313 2020-10-25T19:57:33 Z VROOM_VARUN Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 262148 KB 
/*
ID: varunra2
LANG: C++
TASK: wombat
*/

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

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

int n, m;
int siz;

bool sub1 = false;
bool sub23 = false;
bool sub4 = false;

int ret = 0;

int hsh(int i, int j) { return i * m + j; }

PII unhsh(int h) { return MP(h / m, h % m); }

VVI h(5001, VI(201));
VVI v(5001, VI(201));
int dp[2][2][5001];

vector<VII> adj;

void addEdge(int i, int j, int k, int l, int w, bool b = false) {
  int u = hsh(i, j);
  int v = hsh(k, l);
  adj[u].PB(MP(v, w));
  if (b) adj[v].PB(MP(u, w));
}

void genAdj() {
  adj.resize(siz);
  trav(x, adj) x.clear();
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < m; j++) {
      addEdge(i, j, i + 1, j, v[i][j]);
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m - 1; j++) {
      addEdge(i, j, i, j + 1, h[i][j], true);
    }
  }
}

void calc(int ind) {
  for (int i = 1; i < n; i++) {
    int j = i - 1;
    for(int k = 0; k < 2; k++) {
      dp[ind][k][i] = min(dp[ind][k][j] + v[j][k], dp[ind][k ^ 1][j] + v[j][k ^ 1] + h[i][0]);
    }
  }
}

void calcDP() {
  rep(i, 0, 2) rep(j, 0, 2) rep(k, 0, 5001) dp[i][j][k] = INF;
  dp[0][0][0] = 0;
  dp[1][1][0] = 0;
  calc(0);
  calc(1);
}

VI dijk(int src) {
  VI dist(siz, 2 * INF);
  dist[src] = 0;
  priority_queue<PII, VII, greater<PII>> pq;
  pq.push(MP(0, src));
  vector<bool> vis(siz, false);
  while (!pq.empty()) {
    int u = pq.top().y;
    int d = pq.top().x;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (auto& x : adj[u]) {
      if (dist[u] + x.y < dist[x.x]) {
        dist[x.x] = dist[u] + x.y;
        pq.push(MP(dist[x.x], x.x));
      }
    }
  }
  return dist;
}

VVI mem;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
  if (C == 1)
    sub1 = true;
  else if (C == 2)
    sub23 = true;
  else
    sub23 = true;
  n = R;
  m = C;
  siz = n * m;
  mem.resize(m);
  for (int i = 0; i < 5000; i++) {
    for (int j = 0; j < 200; j++) {
      h[i][j] = H[i][j];
      v[i][j] = V[i][j];
    }
  }
  if (sub23) genAdj();
  if (sub1)
    for (int i = 0; i < 5000; i++) {
      ret += v[i][0];
    }
  if (sub4) {
    calcDP();
  }
}

void changeV(int p, int q, int w) {
  trav(x, mem) x.clear();
  if (sub1) {
    ret -= v[p][q];
    ret += w;
  }
  v[p][q] = w;
  if (sub23) genAdj();
  if(sub4) calcDP();
}

void changeH(int p, int q, int w) {
  trav(x, mem) x.clear();
  if (sub1) {
    ret -= h[p][q];
    ret += w;
  }
  h[p][q] = w;
  if (sub23) genAdj();
  if(sub4) calcDP();
}

int escape(int a, int b) {
  if (sub1) return ret;
  if(sub23) {
    int u = hsh(0, a);
    int v = hsh(n - 1, b);
    if(sz(mem[u])) {
      return mem[u][v];
    }
    mem[u] = dijk(u);
    return mem[u][v];
  }
  if (sub4) return dp[a][b][n - 1];
}

// int main() {
// #ifndef ONLINE_JUDGE
//   freopen("wombat.in", "r", stdin);
//   freopen("wombat.out", "w", stdout);
// #endif
//   cin.sync_with_stdio(0);
//   cin.tie(0);

//   int r, c;
//   int h[5000][200];
//   int v[5000][200];

//   cin >> r >> c;

//   rep(i, 0, r) rep(j, 0, c - 1) cin >> h[i][j];
//   rep(i, 0, r - 1) rep(j, 0, c) cin >> v[i][j];

//   init(r, c, h, v);
//   debug("done");
//   int q;
//   cin >> q;

//   while (q--) {
//     int type;
//     cin >> type;
//     if (type == 0) {
//       int a, b;
//       cin >> a >> b;
//       cout << escape(a, b) << '\n';
//     } else if (type == 1) {
//       int p, q, w;
//       cin >> p >> q >> w;
//       changeV(p, q, w);
//     } else {
//       int p, q, w;
//       cin >> p >> q >> w;
//       changeH(p, q, w);
//     }
//     debug("done", type);
//   }

//   return 0;
// }

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'VI dijk(int)':
wombats.cpp:122:9: warning: unused variable 'd' [-Wunused-variable]
  122 |     int d = pq.top().x;
      |         ^
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:199:1: warning: control reaches end of non-void function [-Wreturn-type]
  199 | }
      | ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12416 KB Output is correct
2 Correct 11 ms 12416 KB Output is correct
3 Correct 95 ms 14200 KB Output is correct
4 Correct 11 ms 12416 KB Output is correct
5 Correct 11 ms 12416 KB Output is correct
6 Correct 8 ms 8576 KB Output is correct
7 Correct 8 ms 8576 KB Output is correct
8 Correct 8 ms 8576 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8576 KB Output is correct
2 Correct 9 ms 8576 KB Output is correct
3 Correct 8 ms 8576 KB Output is correct
4 Correct 9 ms 8704 KB Output is correct
5 Correct 9 ms 8704 KB Output is correct
6 Correct 9 ms 8704 KB Output is correct
7 Correct 10 ms 8704 KB Output is correct
8 Correct 12 ms 8704 KB Output is correct
9 Correct 9 ms 8704 KB Output is correct
10 Correct 10 ms 8704 KB Output is correct
11 Correct 93 ms 9648 KB Output is correct
12 Correct 10 ms 8704 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 12152 KB Output is correct
2 Correct 278 ms 11888 KB Output is correct
3 Correct 199 ms 12024 KB Output is correct
4 Correct 203 ms 12152 KB Output is correct
5 Correct 205 ms 12152 KB Output is correct
6 Correct 8 ms 8576 KB Output is correct
7 Correct 8 ms 8576 KB Output is correct
8 Correct 8 ms 8576 KB Output is correct
9 Correct 293 ms 9720 KB Output is correct
10 Correct 9 ms 8576 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 17024 KB Output is correct
2 Correct 1303 ms 17272 KB Output is correct
3 Correct 637 ms 17272 KB Output is correct
4 Correct 682 ms 18552 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 12152 KB Output is correct
2 Correct 276 ms 11896 KB Output is correct
3 Correct 200 ms 12280 KB Output is correct
4 Correct 200 ms 12024 KB Output is correct
5 Correct 197 ms 12024 KB Output is correct
6 Correct 640 ms 17228 KB Output is correct
7 Correct 1311 ms 17400 KB Output is correct
8 Correct 631 ms 17272 KB Output is correct
9 Correct 684 ms 18512 KB Output is correct
10 Correct 11 ms 12416 KB Output is correct
11 Correct 11 ms 12544 KB Output is correct
12 Correct 94 ms 15224 KB Output is correct
13 Correct 11 ms 12544 KB Output is correct
14 Correct 11 ms 12544 KB Output is correct
15 Correct 8 ms 8576 KB Output is correct
16 Correct 8 ms 8576 KB Output is correct
17 Correct 8 ms 8576 KB Output is correct
18 Correct 10 ms 8704 KB Output is correct
19 Correct 9 ms 8704 KB Output is correct
20 Correct 9 ms 8608 KB Output is correct
21 Correct 10 ms 8704 KB Output is correct
22 Correct 10 ms 8704 KB Output is correct
23 Correct 10 ms 8704 KB Output is correct
24 Correct 10 ms 8704 KB Output is correct
25 Correct 96 ms 11012 KB Output is correct
26 Correct 10 ms 8704 KB Output is correct
27 Correct 292 ms 9728 KB Output is correct
28 Execution timed out 20073 ms 253668 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 12152 KB Output is correct
2 Correct 282 ms 12152 KB Output is correct
3 Correct 199 ms 12152 KB Output is correct
4 Correct 199 ms 12152 KB Output is correct
5 Correct 197 ms 12024 KB Output is correct
6 Correct 636 ms 17272 KB Output is correct
7 Correct 1286 ms 17272 KB Output is correct
8 Correct 636 ms 17272 KB Output is correct
9 Correct 691 ms 18552 KB Output is correct
10 Correct 11 ms 12544 KB Output is correct
11 Correct 11 ms 12544 KB Output is correct
12 Correct 94 ms 15224 KB Output is correct
13 Correct 11 ms 12544 KB Output is correct
14 Correct 11 ms 12544 KB Output is correct
15 Correct 1271 ms 108460 KB Output is correct
16 Runtime error 9804 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -