oj.uz

Submission #316263

# Submission time Handle Problem Language Result Execution time Memory
316263 2020-10-25T18:34:25 Z VROOM_VARUN Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 17796 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(5000, VI(200));
VVI v(5000, VI(200));

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);
    }
  }
}

int dijk(int src, int goal) {
  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;
    if (u == goal) return d;
    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 2 * INF;
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
  if (C == 1)
    sub1 = true;
  else if (C == 2)
    sub4 = true;
  else
    sub23 = true;
  n = R;
  m = C;
  siz = n * 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();
  for (int i = 0; i < 5000; i++) {
    ret += v[i][0];
  }
}

void changeV(int p, int q, int w) {
  ret -= v[p][q];
  ret += w;
  v[p][q] = w;
  genAdj();
}

void changeH(int p, int q, int w) {
  ret -= h[p][q];
  ret += w;
  h[p][q] = w;
  genAdj();
}

int escape(int a, int b) {
  if (sub1) return ret;
  if (sub23) return dijk(hsh(0, a), hsh(n - 1, b));
}

// 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");
//   }

//   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 'int escape(int, int)':
wombats.cpp:158:1: warning: control reaches end of non-void function [-Wreturn-type]
  158 | }
      | ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 12792 KB Output is correct
2 Correct 49 ms 12672 KB Output is correct
3 Correct 131 ms 14584 KB Output is correct
4 Correct 49 ms 12800 KB Output is correct
5 Correct 55 ms 12920 KB Output is correct
6 Correct 9 ms 8576 KB Output is correct
7 Correct 10 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 8 ms 8576 KB Output is correct
3 Correct 8 ms 8576 KB Output is correct
4 Correct 24 ms 8576 KB Output is correct
5 Correct 18 ms 8576 KB Output is correct
6 Correct 18 ms 8576 KB Output is correct
7 Correct 24 ms 8576 KB Output is correct
8 Correct 21 ms 8576 KB Output is correct
9 Correct 30 ms 8576 KB Output is correct
10 Correct 23 ms 8576 KB Output is correct
11 Correct 7991 ms 10060 KB Output is correct
12 Correct 31 ms 8576 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 9472 KB Output is correct
2 Correct 200 ms 9828 KB Output is correct
3 Correct 189 ms 9472 KB Output is correct
4 Correct 189 ms 9472 KB Output is correct
5 Correct 189 ms 9472 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 386 ms 9600 KB Output is correct
10 Correct 8 ms 8576 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 17016 KB Output is correct
2 Correct 1246 ms 17144 KB Output is correct
3 Correct 646 ms 17144 KB Output is correct
4 Execution timed out 20052 ms 17528 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 9472 KB Output is correct
2 Correct 212 ms 9708 KB Output is correct
3 Correct 197 ms 9472 KB Output is correct
4 Correct 191 ms 9472 KB Output is correct
5 Correct 196 ms 9576 KB Output is correct
6 Correct 664 ms 17012 KB Output is correct
7 Correct 1283 ms 17024 KB Output is correct
8 Correct 644 ms 16896 KB Output is correct
9 Execution timed out 20021 ms 17568 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 9472 KB Output is correct
2 Correct 200 ms 9652 KB Output is correct
3 Correct 191 ms 9472 KB Output is correct
4 Correct 190 ms 9472 KB Output is correct
5 Correct 186 ms 9472 KB Output is correct
6 Correct 651 ms 17016 KB Output is correct
7 Correct 1265 ms 17272 KB Output is correct
8 Correct 640 ms 17016 KB Output is correct
9 Execution timed out 20039 ms 17796 KB Time limit exceeded
10 Halted 0 ms 0 KB -