oj.uz

Submission #203582

# Submission time Handle Problem Language Result Execution time Memory
203582 2020-02-21T13:40:32 Z galen_colin Wombats (IOI13_wombats) C++14
55 / 100
 2330 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 */
  bitset<1000000> vis;
  vector<vector<pair<int, int> > > edges; /* weight, to */
  
  void init(int s) {
    n = s;
    dists = vector<int>(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);
    vis = bitset<1000000>(0);
 
    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 253 ms 33656 KB Output is correct
2 Correct 263 ms 33656 KB Output is correct
3 Correct 344 ms 35320 KB Output is correct
4 Correct 266 ms 33784 KB Output is correct
5 Correct 251 ms 33656 KB Output is correct
6 Correct 17 ms 25464 KB Output is correct
7 Correct 16 ms 25464 KB Output is correct
8 Correct 17 ms 25464 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25464 KB Output is correct
2 Correct 18 ms 25424 KB Output is correct
3 Correct 17 ms 25464 KB Output is correct
4 Correct 20 ms 26104 KB Output is correct
5 Correct 19 ms 26104 KB Output is correct
6 Correct 18 ms 26104 KB Output is correct
7 Correct 20 ms 26104 KB Output is correct
8 Correct 20 ms 25976 KB Output is correct
9 Correct 19 ms 26104 KB Output is correct
10 Correct 18 ms 26104 KB Output is correct
11 Correct 116 ms 27128 KB Output is correct
12 Correct 20 ms 26104 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 74752 KB Output is correct
2 Correct 395 ms 28812 KB Output is correct
3 Correct 317 ms 29460 KB Output is correct
4 Correct 320 ms 29568 KB Output is correct
5 Correct 302 ms 29440 KB Output is correct
6 Correct 17 ms 25464 KB Output is correct
7 Correct 16 ms 25464 KB Output is correct
8 Correct 16 ms 25464 KB Output is correct
9 Correct 201 ms 27412 KB Output is correct
10 Correct 18 ms 25464 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1624 ms 42516 KB Output is correct
2 Correct 2325 ms 42752 KB Output is correct
3 Correct 1625 ms 42512 KB Output is correct
4 Correct 1637 ms 43444 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 74748 KB Output is correct
2 Correct 382 ms 28808 KB Output is correct
3 Correct 310 ms 29456 KB Output is correct
4 Correct 310 ms 29568 KB Output is correct
5 Correct 305 ms 29440 KB Output is correct
6 Correct 1601 ms 42488 KB Output is correct
7 Correct 2328 ms 43080 KB Output is correct
8 Correct 1675 ms 42624 KB Output is correct
9 Correct 1642 ms 43540 KB Output is correct
10 Correct 253 ms 33656 KB Output is correct
11 Correct 250 ms 33656 KB Output is correct
12 Correct 340 ms 35224 KB Output is correct
13 Correct 262 ms 33656 KB Output is correct
14 Correct 253 ms 33784 KB Output is correct
15 Correct 17 ms 25464 KB Output is correct
16 Correct 17 ms 25464 KB Output is correct
17 Correct 17 ms 25464 KB Output is correct
18 Correct 20 ms 26104 KB Output is correct
19 Correct 18 ms 26108 KB Output is correct
20 Correct 21 ms 26104 KB Output is correct
21 Correct 19 ms 26104 KB Output is correct
22 Correct 19 ms 25976 KB Output is correct
23 Correct 19 ms 26104 KB Output is correct
24 Correct 20 ms 25976 KB Output is correct
25 Correct 108 ms 27128 KB Output is correct
26 Correct 21 ms 26104 KB Output is correct
27 Correct 193 ms 27320 KB Output is correct
28 Runtime error 1133 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 246 ms 74880 KB Output is correct
2 Correct 391 ms 28812 KB Output is correct
3 Correct 314 ms 29464 KB Output is correct
4 Correct 307 ms 29568 KB Output is correct
5 Correct 312 ms 29512 KB Output is correct
6 Correct 1614 ms 42620 KB Output is correct
7 Correct 2330 ms 42744 KB Output is correct
8 Correct 1620 ms 42492 KB Output is correct
9 Correct 1665 ms 43600 KB Output is correct
10 Correct 250 ms 33656 KB Output is correct
11 Correct 257 ms 33656 KB Output is correct
12 Correct 344 ms 35320 KB Output is correct
13 Correct 255 ms 33656 KB Output is correct
14 Correct 255 ms 33784 KB Output is correct
15 Correct 1747 ms 189708 KB Output is correct
16 Runtime error 1131 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -