oj.uz

답안 #316258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
316258 2020-10-25T18:27:41 Z VROOM_VARUN 웜뱃 (IOI13_wombats) C++14
28 / 100
 20000 ms 18112 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;

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]) {
  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];
    }
  }
  genAdj();
}

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

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

int escape(int a, int b) { 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;
      |      ^~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 12824 KB Output is correct
2 Correct 125 ms 12800 KB Output is correct
3 Execution timed out 20055 ms 15132 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 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 19 ms 8576 KB Output is correct
7 Correct 24 ms 8576 KB Output is correct
8 Correct 22 ms 8576 KB Output is correct
9 Correct 25 ms 8576 KB Output is correct
10 Correct 23 ms 8576 KB Output is correct
11 Correct 8125 ms 11236 KB Output is correct
12 Correct 34 ms 8576 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 9600 KB Output is correct
2 Correct 200 ms 9732 KB Output is correct
3 Correct 191 ms 9600 KB Output is correct
4 Correct 189 ms 9600 KB Output is correct
5 Correct 211 ms 9600 KB Output is correct
6 Correct 9 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 9 ms 8576 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 638 ms 17096 KB Output is correct
2 Correct 1255 ms 17144 KB Output is correct
3 Correct 643 ms 17148 KB Output is correct
4 Execution timed out 20058 ms 17952 KB Time limit exceeded

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 9600 KB Output is correct
2 Correct 204 ms 9828 KB Output is correct
3 Correct 198 ms 9600 KB Output is correct
4 Correct 190 ms 9600 KB Output is correct
5 Correct 186 ms 9728 KB Output is correct
6 Correct 635 ms 17144 KB Output is correct
7 Correct 1262 ms 17144 KB Output is correct
8 Correct 635 ms 17024 KB Output is correct
9 Execution timed out 20089 ms 17784 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 9600 KB Output is correct
2 Correct 208 ms 9720 KB Output is correct
3 Correct 191 ms 9600 KB Output is correct
4 Correct 188 ms 9600 KB Output is correct
5 Correct 186 ms 9600 KB Output is correct
6 Correct 653 ms 17080 KB Output is correct
7 Correct 1285 ms 17024 KB Output is correct
8 Correct 651 ms 17080 KB Output is correct
9 Execution timed out 20017 ms 18112 KB Time limit exceeded
10 Halted 0 ms 0 KB -