oj.uz

Submission #203580

# Submission time Handle Problem Language Result Execution time Memory
203580 2020-02-21T13:33:28 Z galen_colin Wombats (IOI13_wombats) C++14
55 / 100
 2228 ms 262148 KB 
#include <bits/stdc++.h>
#include <chrono> 
 
using namespace std;
using namespace std::chrono; 
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma optimization_level 3
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define f0r(a, b) for (long long a = 0; a < (b); a++)
#define f1r(a, b, c) for (long long a = (b); a < (c); a++)
#define f0rd(a, b) for (long long a = (b); a >= 0; a--)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define io {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define mp make_pair
#define f first
#define s second
#define presum(p, a, n) {p[0] = a[0]; for (int i = 1; i < (n); i++) p[i] = a[i] + p[i-1];}
#define all(v) v.begin(), v.end()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
#define ai(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];
#define ain(a, lb, rb) for (int ele = lb; ele <= rb; ele++) cin >> a[ele];
#define ao(a, n) {for (int ele = 0; ele < n; ele++) { if (ele) cout << " "; cout << a[ele]; } cout << '\n';}
#define aout(a, lb, rb) {for (int ele = lb; ele <= rb; ele++) { if (ele > lb) cout << " "; cout << a[ele]; } cout << '\n';}
typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
  cin >> p.first;
  return cin >> p.second;
}
 
// template<typename A, typename B> ll max(A x, B y) {
//   return x > y ? x : y;
// }
// template<typename A, typename B> ll min(A x, B y) {
//   return x < y ? x : y;
// }
 
mt19937 rng(steady_clock::now().time_since_epoch().count());
/* usage - just do rng() */
 
void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
 
// void init(int r, int c, int h[5000][200], int v[5000][200]);
 
// void changeH(int r, int c, int w);
 
// void changeV(int r, int c, int w);
 
// int escape(int c1, int c2);
 
// #define fail(s, x...) do { \
// 		fprintf(stderr, s "\n", ## x); \
// 		exit(1); \
// 	} while(0)
 
// static int H[5000][200];
// static int V[5000][200];
 
// int main() {
// 	int R, C, E, P, Q, W, V1, V2, event, i, j;
// 	int res;
 
// 	FILE *f = fopen("file.in", "r");
// 	if (!f)
// 		fail("Failed to open input file.");
 
// 	res = fscanf(f, "%d%d", &R, &C);
//     for (i = 0; i < R; ++i)
//         for (j = 0; j < C-1; ++j)
//             res = fscanf(f, "%d", &H[i][j]);
//     for (i = 0; i < R-1; ++i)
//         for (j = 0; j < C; ++j)
//             res = fscanf(f, "%d", &V[i][j]);
 
//     init(R, C, H, V);
 
// 	res = fscanf(f, "%d", &E);
// 	for (i = 0; i < E; i++) {
// 		res = fscanf(f, "%d", &event);
//         if (event == 1) {
//             res = fscanf(f, "%d%d%d", &P, &Q, &W);
//             changeH(P, Q, W);
//         } else if (event == 2) {
//             res = fscanf(f, "%d%d%d", &P, &Q, &W);
//             changeV(P, Q, W);
//         } else if (event == 3) {
//             res = fscanf(f, "%d%d", &V1, &V2);
//             printf("%d\n", escape(V1, V2));
//         } else
//             fail("Invalid event type.");
// 	}
 
// 	fclose(f);
// 	return 0;
// }
 
#include "wombats.h"
 
struct dijkstra {
  int n;
  const int inf = 1.1e9;
  vector<int> dists; /* for a single run */
  vector<bool> vis;
  vector<vector<pair<int, int> > > edges; /* weight, to */
  
  void init(int s) {
    n = s;
    dists = vector<int>(n);
	  vis = vector<bool>(n);
    edges = vector<vector<pair<int, int> > >(n);
  }
 
  void edge(int a, int b, int wt) {
    edges[a].push_back(make_pair(wt, b));
  }
 
  using ptype = pair<int, int>;
  void run(int src) {
    fill(dists.begin(), dists.end(), inf);
	  fill(vis.begin(), vis.end(), false);
 
    priority_queue<ptype, vector<ptype>, greater<ptype>> pq;
    dists[src] = 0;
    pq.push(make_pair(0, src));
    while (!pq.empty()) {
      ptype foc = pq.top();
      pq.pop();
	  
	    if (vis[foc.s]) continue;
	    vis[foc.s] = 1;
	  
      dists[foc.s] = min(dists[foc.s], foc.f);
      for (ptype x: edges[foc.s]) {
        ll d = dists[foc.s] + x.f;
        if (d < dists[x.s]) {
          dists[x.s] = d;
          pq.push(make_pair(d, x.s));
        }
      }
    }
  }
};
 
ll n, m, k, q, Q, T, l, r, x, y, z;
ll a[1000005];
ll b[1000005];
ll c[1000005];
string s, t;
ll ans = 0;
 
int hh[5005][205];
int vv[5005][205];
dijkstra dd[205];
bool ready[205];

void init_d(int i) {
  if (ready[i]) return;
  ready[i] = 1;

  dd[i].init(n * m);
  f0r(j, n) {
    f0r(k, m) {
      int id = j * m + k;
      if (k != 0) dd[i].edge(id, id - 1, hh[j][k - 1]);
      if (k != m - 1) dd[i].edge(id, id + 1, hh[j][k]);
      if (j != n - 1) dd[i].edge(id, id + m, vv[j][k]);
    }
  }
  dd[i].run(i);
}

void recomp() {
  ms(ready, 0);
  f0r(i, m) dd[i].init(1);
}
 
void init(int r, int c, int h[5000][200], int v[5000][200]) {
  n = r;
  m = c;
  f0r(i, n) f0r(j, m - 1) {
    hh[i][j] = h[i][j];
  }
  f0r(i, n - 1) f0r(j, m) {
    vv[i][j] = v[i][j];
  }
  recomp();
  // f0r(i, m) cout << dd[i].dists << endl;
}
 
void changeH(int r, int c, int w) {
  hh[r][c] = w;
  recomp();
}
 
void changeV(int r, int c, int w) {
  vv[r][c] = w;
  recomp();
}
 
int escape(int c1, int c2) {
  if (!ready[c1]) init_d(c1);
  return dd[c1].dists[(n - 1) * m + c2];
}
 
// int main() {
//   io;
//   // freopen("case", "r", stdin);
//   // freopen("test.txt", "r", stdin);
//   // freopen("case", "w", stdout);
//   // freopen("file.in", "r", stdin);
 
//   // usaco("file");
 
  
// }

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
wombats.cpp:81:1: warning: multi-line comment [-Wcomment]
 // #define fail(s, x...) do { \
 ^
wombats.cpp: In function 'void usaco(std::__cxx11::string)':
wombats.cpp:65:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".in").c_str(), "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:66:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".out").c_str(), "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 8568 KB Output is correct
2 Correct 233 ms 8572 KB Output is correct
3 Correct 318 ms 10232 KB Output is correct
4 Correct 237 ms 8696 KB Output is correct
5 Correct 245 ms 8696 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 8 ms 1064 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 7 ms 1016 KB Output is correct
7 Correct 7 ms 1016 KB Output is correct
8 Correct 7 ms 888 KB Output is correct
9 Correct 7 ms 1016 KB Output is correct
10 Correct 7 ms 760 KB Output is correct
11 Correct 98 ms 2040 KB Output is correct
12 Correct 8 ms 1016 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 49796 KB Output is correct
2 Correct 370 ms 3632 KB Output is correct
3 Correct 288 ms 4500 KB Output is correct
4 Correct 285 ms 4460 KB Output is correct
5 Correct 289 ms 4456 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 182 ms 2208 KB Output is correct
10 Correct 5 ms 376 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1533 ms 17560 KB Output is correct
2 Correct 2228 ms 17728 KB Output is correct
3 Correct 1525 ms 17556 KB Output is correct
4 Correct 1560 ms 18272 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 49792 KB Output is correct
2 Correct 366 ms 3756 KB Output is correct
3 Correct 280 ms 4372 KB Output is correct
4 Correct 284 ms 4352 KB Output is correct
5 Correct 285 ms 4352 KB Output is correct
6 Correct 1493 ms 17428 KB Output is correct
7 Correct 2198 ms 17612 KB Output is correct
8 Correct 1477 ms 17428 KB Output is correct
9 Correct 1540 ms 18452 KB Output is correct
10 Correct 229 ms 8568 KB Output is correct
11 Correct 241 ms 8564 KB Output is correct
12 Correct 325 ms 10232 KB Output is correct
13 Correct 235 ms 8568 KB Output is correct
14 Correct 239 ms 8568 KB Output is correct
15 Correct 5 ms 380 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 8 ms 1016 KB Output is correct
19 Correct 7 ms 1016 KB Output is correct
20 Correct 7 ms 1016 KB Output is correct
21 Correct 7 ms 1016 KB Output is correct
22 Correct 7 ms 888 KB Output is correct
23 Correct 7 ms 1016 KB Output is correct
24 Correct 7 ms 888 KB Output is correct
25 Correct 91 ms 2040 KB Output is correct
26 Correct 7 ms 1016 KB Output is correct
27 Correct 181 ms 2268 KB Output is correct
28 Runtime error 1242 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 49788 KB Output is correct
2 Correct 364 ms 3632 KB Output is correct
3 Correct 284 ms 4372 KB Output is correct
4 Correct 280 ms 4480 KB Output is correct
5 Correct 282 ms 4352 KB Output is correct
6 Correct 1496 ms 17552 KB Output is correct
7 Correct 2205 ms 17588 KB Output is correct
8 Correct 1502 ms 17556 KB Output is correct
9 Correct 1541 ms 18224 KB Output is correct
10 Correct 230 ms 8700 KB Output is correct
11 Correct 233 ms 8696 KB Output is correct
12 Correct 317 ms 10232 KB Output is correct
13 Correct 235 ms 8572 KB Output is correct
14 Correct 231 ms 8568 KB Output is correct
15 Correct 1691 ms 164856 KB Output is correct
16 Runtime error 1322 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -