oj.uz

Submission #203588

# Submission time Handle Problem Language Result Execution time Memory
203588 2020-02-21T14:12:18 Z galen_colin Wombats (IOI13_wombats) C++14
55 / 100
 2047 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;
  int dists[500005]; /* for a single run */
  bitset<500000> vis;
  vector<vector<pair<int, int> > > edges; /* weight, to */
  
  void init(int s) {
    n = s;
    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) {
    for (int i = 0; i < n; i++) dists[i] = inf;
    vis = bitset<500000>(0);
 
    set<ptype> s;
    dists[src] = 0;
    s.insert(make_pair(0, src));
    while (!s.empty()) {
      ptype foc = *s.begin();
      s.erase(s.begin());
	  
	    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]) {
          auto it = s.find(make_pair(dists[x.s], x.s));
          if (it != s.end()) s.erase(it);
          dists[x.s] = d;
          s.insert(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 278 ms 22904 KB Output is correct
2 Correct 276 ms 22648 KB Output is correct
3 Correct 369 ms 24824 KB Output is correct
4 Correct 277 ms 22648 KB Output is correct
5 Correct 290 ms 22648 KB Output is correct
6 Correct 13 ms 14456 KB Output is correct
7 Correct 13 ms 14456 KB Output is correct
8 Correct 13 ms 14456 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 13 ms 14456 KB Output is correct
3 Correct 13 ms 14456 KB Output is correct
4 Correct 16 ms 15096 KB Output is correct
5 Correct 15 ms 15096 KB Output is correct
6 Correct 16 ms 15096 KB Output is correct
7 Correct 16 ms 15096 KB Output is correct
8 Correct 16 ms 15096 KB Output is correct
9 Correct 16 ms 15096 KB Output is correct
10 Correct 16 ms 15100 KB Output is correct
11 Correct 101 ms 16632 KB Output is correct
12 Correct 16 ms 15100 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 63960 KB Output is correct
2 Correct 456 ms 20020 KB Output is correct
3 Correct 433 ms 20924 KB Output is correct
4 Correct 439 ms 20864 KB Output is correct
5 Correct 415 ms 20480 KB Output is correct
6 Correct 13 ms 14456 KB Output is correct
7 Correct 13 ms 14456 KB Output is correct
8 Correct 15 ms 14456 KB Output is correct
9 Correct 214 ms 16532 KB Output is correct
10 Correct 13 ms 14456 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1977 ms 31608 KB Output is correct
2 Correct 1990 ms 31596 KB Output is correct
3 Correct 1978 ms 31608 KB Output is correct
4 Correct 2017 ms 32788 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 63872 KB Output is correct
2 Correct 455 ms 20044 KB Output is correct
3 Correct 423 ms 20836 KB Output is correct
4 Correct 424 ms 21120 KB Output is correct
5 Correct 418 ms 20476 KB Output is correct
6 Correct 1952 ms 31636 KB Output is correct
7 Correct 1976 ms 31636 KB Output is correct
8 Correct 1980 ms 31720 KB Output is correct
9 Correct 2047 ms 33084 KB Output is correct
10 Correct 289 ms 22776 KB Output is correct
11 Correct 274 ms 22776 KB Output is correct
12 Correct 380 ms 24824 KB Output is correct
13 Correct 281 ms 22648 KB Output is correct
14 Correct 295 ms 22768 KB Output is correct
15 Correct 13 ms 14456 KB Output is correct
16 Correct 13 ms 14456 KB Output is correct
17 Correct 14 ms 14456 KB Output is correct
18 Correct 16 ms 15096 KB Output is correct
19 Correct 16 ms 15096 KB Output is correct
20 Correct 15 ms 15096 KB Output is correct
21 Correct 16 ms 15096 KB Output is correct
22 Correct 16 ms 15096 KB Output is correct
23 Correct 16 ms 15096 KB Output is correct
24 Correct 16 ms 15096 KB Output is correct
25 Correct 102 ms 16632 KB Output is correct
26 Correct 17 ms 15224 KB Output is correct
27 Correct 213 ms 16532 KB Output is correct
28 Runtime error 1350 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 333 ms 64004 KB Output is correct
2 Correct 462 ms 20148 KB Output is correct
3 Correct 431 ms 20804 KB Output is correct
4 Correct 428 ms 20864 KB Output is correct
5 Correct 423 ms 20480 KB Output is correct
6 Correct 1989 ms 31608 KB Output is correct
7 Correct 1941 ms 31508 KB Output is correct
8 Correct 1977 ms 31616 KB Output is correct
9 Correct 2008 ms 33076 KB Output is correct
10 Correct 280 ms 22776 KB Output is correct
11 Correct 278 ms 22648 KB Output is correct
12 Correct 366 ms 24824 KB Output is correct
13 Correct 289 ms 22776 KB Output is correct
14 Correct 286 ms 22772 KB Output is correct
15 Runtime error 539 ms 211416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -