Submission #1165916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165916		sano	Wombats (IOI13_wombats)	C++20	55 / 100	10020 ms	327680 KiB

wombats

#include "wombats.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 2000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;



class intervalac {
	int n;
	vec<int> l, r;
	vec<vec<vec<int>>> in;
	int c;
	vec<vec<int>> h, v;
public:
	void postav(int x, vec<int>& h1, vec<int>& h2, vec<int>& v) {
		if (in[x].empty()) return;
		For(i, c) {
			//cout << "bol som c " << i << '\n';
			priority_queue<pii> q;
			vec<bool> bol(2 * c, 0);
			q.push({ 0, i });
			while (!q.empty()) {
				int som = q.top().ss, d = q.top().ff; q.pop();
				//cout << "bol som d " << som << ' ' << d << '\n';
				if (som == 18 && d == 0 && i == 0) {
					int lol = 1;
				}
				if (bol[som]) continue;
				d *= (-1);
				bol[som] = 1;
				int nd = 0;
				int pos = 0;
				if (som >= c) {
					pos = c;
					swap(h1, h2);
				}
				int nsom = 0;
				if (som + 1 - pos != c) {
					nsom = som + 1;
					nd = d + h1[nsom - pos - 1];
					q.push({ (-1) * nd, nsom });
				}
				if (som - 1 - pos >= 0) {
					nsom = som - 1;
					nd = d + h1[nsom - pos];
					q.push({ (-1) * nd, nsom });
				}
				if (som < c) {
					nsom = som + c;
					nd = d + v[som];
					q.push({ (-1) * nd, nsom });
				}
				else {
					in[x][i][som - c] = d;
				}
				if (som >= c) swap(h1, h2);
			}
		}
	}
	void update(int x) {
		if (in[2 * x + 1].empty()) {
			in[x] = in[2 * x];
			return;
		}
		if (in[x].empty()) in[x].resize(c, vec<int>(c));
		For(i, in[2 * x].size()) {
			For(j, in[2 * x + 1].size()) {
				in[x][i][j] = NEK;
				For(r, in[2 * x].size()) {
					in[x][i][j] = min(in[x][i][j], in[2 * x][i][r] + in[2 * x + 1][r][j]);
				}
			}
		}
		return;
	}
	void zaciatok(int r1, int c1, vec<vec<int>>& h1, vec<vec<int>>& v1) {
		l.clear(); r.clear(); in.clear(); h.clear(); v.clear();
		c = c1;
		n = 1;
		h = h1;
		v = v1;
		while (n < (r1 - 1)) n *= 2;
		l.resize(2 * n); r.resize(2 * n);
		if (h.size() < (n + 1)) h.resize(n + 1, vec<int>(c1 - 1, 0));
		if (v.size() < n) v.resize(n, vec<int>(c1, 0));
		in.resize(2*n);
		For(i, (r1 - 1)) {
			in[i + n].resize(c, vec<int>(c));
		}
		For(i, n) {
			l[i + n] = i;
			r[i + n] = i;
			postav(i + n, h[i], h[i + 1], v[i]);
		}
		rffor(i, 1, (n - 1)) {
			l[i] = l[i * 2];
			r[i] = r[i * 2 + 1];
			update(i);
		}
	}
	int daj(int a, int b) {
		return in[1][a][b];
	}
	void zmenh(int p, int q, int w) {
		h[p][q] = w;
		int som1 = 0, som2 = 0;
		if (p != (h.size() - 1)) {
			postav(p + n, h[p], h[p + 1], v[p]);
			som1 = p + n;
		}
		if (p != 0) {
			postav(p + n - 1, h[p - 1], h[p], v[p - 1]);
			som2 = p + n - 1;
		}
		som1 /= 2;
		som2 /= 2;
		while (som1) {
			update(som1);
			som1 /= 2;
		}
		while (som2) {
			update(som2);
			som2 /= 2;
		}
		return;
	}
	void zmenv(int p, int q, int w) {
		v[p][q] = w;
		postav(p + n, h[p], h[p + 1], v[p]);
		int som = p + n;
		som /= 2;
		while (som) {
			update(som);
			som /= 2;
		}
		return;
	}

};

intervalac seg;

int escape(int v1, int v2) {
	return seg.daj(v1, v2);
}

void changeH(int p, int q, int w) {
	seg.zmenh(p, q, w);
	return;
}

void changeV(int p, int q, int w) {
	seg.zmenv(p, q, w);
	return;
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	int r = R, c = C;
	vec<vec<int>> h(r, vec<int>(c - 1));
	vec<vec<int>> v(r - 1, vec<int>(c));
	For(i, r) {
		For(j, c - 1) {
			h[i][j] = H[i][j];
		}
	}
	For(i, r - 1) {
		For(j, c) {
			v[i][j] = V[i][j];
		}
	}
	seg.zaciatok(r, c, h, v);
	return;
}












//*************************************************************************************************





vec<vec<int>> H, V;
vec<vec<int>> p;
int r, c;
set<int> umap;

struct policko {
	int d, x, y;
	bool operator<(const policko& other) const {
		return d > other.d;
	}
};

void vypocitaj(int s) {
	p[s].resize(c, NEK);
	priority_queue<policko> q;
	q.push({ 0, 0, s });
	vec<vec<bool>> bol(r, vec<bool>(c, 0));
	while (!q.empty()) {
		int d = q.top().d, x = q.top().x, y = q.top().y; q.pop();
		if (bol[x][y]) continue;
		bol[x][y] = 1;
		if (y - 1 >= 0) {
			q.push({ d + H[x][y-1], x, y - 1 });
		}
		if (y + 1 < c) {
			q.push({ d + H[x][y], x, y + 1 });
		}
		if (x < r - 1) {
			q.push({ d + V[x][y], x + 1, y });
		}
		else {
			p[s][y] = d;
		}
	}
	umap.insert(s);
	return;
}

int escape1(int v1, int v2) {
	if (umap.find(v1) == umap.end()) {
		vypocitaj(v1);
	}
	return p[v1][v2];
}

void changeH1(int p1, int q1, int w) {
	H[p1][q1] = w;
	umap.clear();
	return;
}

void changeV1(int p1, int q1, int w) {
	V[p1][q1] = w;
	umap.clear();
	return;
}

void init1(int R, int C, int H1[50][20], int V1[50][20]) {
	H.clear(), V.clear(), p.clear(), umap.clear();
	r = R; c = C;
	H.resize(r, vec<int>(c - 1, 0));
	V.resize(r - 1, vec<int>(c, 0));
	p.resize(c);
	For(i, r) {
		For(j, (c - 1)) {
			H[i][j] = H1[i][j];
		}
	}
	For(i, r - 1) {
		For(j, c) {
			V[i][j] = V1[i][j];
		}
	}

	return;
}


void vypis(int r, int c, int h[50][20], int v[50][20], vec<vec<int>>& ot, int odp1, int odp2) {
	cout << r << ' ' << c << '\n';
	For(i, r) {
		For(j, c - 1) {
			cout << h[i][j] << " \n"[j == c - 2];
		}
	}
	For(i, r - 1) {
		For(j, c) {
			cout << v[i][j] << " \n"[j == c - 1];
		}
	}
	For(i, ot.size()) {
		For(j, ot[i].size()) {
			cout << ot[i][j] << " \n"[j == ot[i].size() - 1];
		}
	}
	cout << odp1 << ' ' << odp2 << '\n';
	return;
}
/*
signed main() {
	ll t;
	//cin >> t;
	t = 1000000000;
	For(w, t) {
		cout << w << '\n';
		int r, c;
		//cin >> r >> c;
		r = rand() % 10 + 2, c = rand() % 10 + 2;
		int h[50][20];
		int v[50][20];
		For(i, r) {
			For(j, (c-1)) {
				h[i][j] = rand() % 100;
				//cin >> h[i][j];
			}
		}
		For(i, (r-1)) {
			For(j, c) {
				v[i][j] = rand() % 100;
				//cin >> v[i][j];
			}
		}
		init1(r, c, h, v);
		init2(r, c, h, v);
		int e;
		//cin >> e;
		e = rand() % 100;
		vec<vec<int>> ot;
		For(i, e) {
			int a, b, d;
			//cin >> a >> b >> d;
			a = rand() % 3 + 1;
			if (a == 3) {
				b = rand() % c, d = rand() % c;
			}
			if (a == 2) {
				b = rand() % (r - 1), d = rand() % c;
			}
			if (a == 1) {
				b = rand() % r, d = rand() % (c - 1);
			}
			ot.push_back({ a, b, d });
			if (a == 1) {
				int f;
				//cin >> f;
				f = rand() % 100;
				changeH1(b, d, f);
				changeH2(b, d, f);
			}
			if (a == 2) {
				int f;
				//cin >> f;
				f = rand() % 100;
				changeV1(b, d, f);
				changeV2(b, d, f);
			}
			if (a == 3) {
				int odp1 = escape1(b, d);
				int odp2 = escape2(b, d);
				if (odp1 != odp2) {
					vypis(r, c, h, v, ot, odp1, odp2);
					return 0;
				}
				//cout << odp1 << '\n';
			}
		}
	}
	return 0;
}*/

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24