답안 #203578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203578	2020-02-21T13:11:36 Z	galen_colin	웜뱃 (IOI13_wombats)	C++14	55 / 100	2226 ms	262148 KB

wombats

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

#	결과	실행 시간	메모리	Grader output
1	Correct	248 ms	8928 KB	Output is correct
2	Correct	240 ms	8916 KB	Output is correct
3	Correct	335 ms	11548 KB	Output is correct
4	Correct	248 ms	8820 KB	Output is correct
5	Correct	247 ms	8924 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

#	결과	실행 시간	메모리	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	1016 KB	Output is correct
5	Correct	8 ms	1016 KB	Output is correct
6	Correct	7 ms	1016 KB	Output is correct
7	Correct	8 ms	1020 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	888 KB	Output is correct
11	Correct	96 ms	3440 KB	Output is correct
12	Correct	8 ms	1016 KB	Output is correct

Subtask #3

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	232 ms	50632 KB	Output is correct
2	Correct	392 ms	45060 KB	Output is correct
3	Correct	311 ms	48016 KB	Output is correct
4	Correct	308 ms	48412 KB	Output is correct
5	Correct	312 ms	47892 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	177 ms	2728 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct

Subtask #4

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1555 ms	18140 KB	Output is correct
2	Correct	2226 ms	18176 KB	Output is correct
3	Correct	1546 ms	18064 KB	Output is correct
4	Correct	1612 ms	19496 KB	Output is correct

Subtask #5

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	225 ms	50628 KB	Output is correct
2	Correct	417 ms	45064 KB	Output is correct
3	Correct	329 ms	47904 KB	Output is correct
4	Correct	311 ms	48404 KB	Output is correct
5	Correct	302 ms	48024 KB	Output is correct
6	Correct	1558 ms	18572 KB	Output is correct
7	Correct	2204 ms	18176 KB	Output is correct
8	Correct	1561 ms	18228 KB	Output is correct
9	Correct	1582 ms	19448 KB	Output is correct
10	Correct	244 ms	8932 KB	Output is correct
11	Correct	244 ms	8888 KB	Output is correct
12	Correct	328 ms	11612 KB	Output is correct
13	Correct	245 ms	8908 KB	Output is correct
14	Correct	245 ms	8820 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	1020 KB	Output is correct
19	Correct	7 ms	1016 KB	Output is correct
20	Correct	7 ms	1020 KB	Output is correct
21	Correct	9 ms	1016 KB	Output is correct
22	Correct	7 ms	888 KB	Output is correct
23	Correct	8 ms	1016 KB	Output is correct
24	Correct	7 ms	888 KB	Output is correct
25	Correct	99 ms	3448 KB	Output is correct
26	Correct	8 ms	1016 KB	Output is correct
27	Correct	175 ms	2728 KB	Output is correct
28	Runtime error	1298 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

#	결과	실행 시간	메모리	Grader output
1	Correct	234 ms	50884 KB	Output is correct
2	Correct	386 ms	45188 KB	Output is correct
3	Correct	311 ms	47928 KB	Output is correct
4	Correct	304 ms	48408 KB	Output is correct
5	Correct	306 ms	47892 KB	Output is correct
6	Correct	1534 ms	18008 KB	Output is correct
7	Correct	2203 ms	18260 KB	Output is correct
8	Correct	1549 ms	18160 KB	Output is correct
9	Correct	1606 ms	19392 KB	Output is correct
10	Correct	256 ms	8820 KB	Output is correct
11	Correct	243 ms	8824 KB	Output is correct
12	Correct	330 ms	11564 KB	Output is correct
13	Correct	242 ms	8820 KB	Output is correct
14	Correct	245 ms	8820 KB	Output is correct
15	Correct	1704 ms	202492 KB	Output is correct
16	Runtime error	1339 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Halted	0 ms	0 KB	-