제출 #203583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203583		galen_colin	웜뱃 (IOI13_wombats)	C++14	55 / 100	2152 ms	262148 KiB

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;
  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);
 
    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");
 
  
// } 

컴파일 시 표준 에러 (stderr) 메시지

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24