Submission #590339

#	Time	Username	Problem	Language	Result	Execution time	Memory
590339		Temmie	Wombats (IOI13_wombats)	C++17	39 / 100	20083 ms	10120 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>

struct Dsu {
	
	std::vector <int> p;
	
	Dsu(int s) {
		p.resize(s);
		std::iota(p.begin(), p.end(), 0);
	}
	
	inline int find(int v) {
		return v == p[v] ? v : (p[v] = find(p[v]));
	}
	
	inline void unite(int u, int v) {
		u = find(u);
		v = find(v);
		p[u] = v;
	}
	
};

int r, c;
std::vector <std::vector <int>> h, v;
std::vector <std::vector <int>> ans;
std::bitset <5000 * 200> vis;

void calculate() {
	for (int s = 0; s < c; s++) {
		vis.reset();
		std::priority_queue <std::pair <int, std::pair <int, int>>> pq;
		pq.push({ 0, { 0, s } });
		while (pq.size()) {
			int w = -pq.top().first;
			int i = pq.top().second.first;
			int j = pq.top().second.second;
			pq.pop();
			if (vis[i * c + j]) {
				continue;
			}
			vis[i * c + j] = 1;
			if (i == r - 1) {
				ans[s][j] = w;
			}
			if (j) pq.push({ -w - h[i][j - 1], { i, j - 1 } });
			if (j + 1 < c) pq.push({ -w - h[i][j], { i, j + 1 } });
			if (i + 1 < r) pq.push({ -w - v[i][j], { i + 1, j } });
		}
	}
}

//void calculate() {
	//ans = std::vector <std::vector <int>> (c, std::vector <int> (c, 1001));
	//Dsu dsu(r * c);
	//std::vector <std::set <int>> reach(r * c);
	//for (int j = 0; j < c; j++) {
		//reach[j].insert(j);
		//reach[(r - 1) * c + j].insert((r - 1) * c + j);
	//}
	//std::vector <std::vector <int>> of(1001);
	//for (int i = 0; i < r; i++) {
		//for (int j = 0; j < c; j++) {
			//if (i < r - 1) {
				//of[v[i][j]].push_back(i * c + j);
			//}
			//if (j < c - 1) {
				//of[h[i][j]].push_back(i * c + j);
			//}
		//}
	//}
	//std::vector <std::set <int>> nodes(r * c);
	//for (int i = 0; i < r; i++) {
		//for (int j = 0; j < c; j++) {
			//nodes[i * c + j].insert(i * c + j);
		//}
	//}
	//for (int k = 0; k <= 1000; k++) {
		//for (int x : of[k]) {
			//int v1 = x;
			//std::vector <int> v2s;
			//if (x / c < r - 1 && v[x / c][x % c] == k) {
				//v2s.push_back(x + c);
			//}
			//if (x % c < c - 1 && h[x / c][x % c] == k) {
				//v2s.push_back(x + 1);
			//}
			//for (int v2 : v2s) {
				//int u1 = dsu.find(v1);
				//int u2 = dsu.find(v2);
				//if (u1 == u2) {
					//continue;
				//}
				//for (int y : reach[u1]) {
					//if (y >= (r - 1) * c) {
						//for (auto it = nodes[u2].begin(); it != nodes[u2].end() && *it < c; it++) {
							//ans[*it][y - (r - 1) * c] = std::min(ans[*it][y - (r - 1) * c], k);
						//}
					//}
				//}
				//for (int y : reach[u2]) {
					//if (y >= (r - 1) * c) {
						//for (auto it = nodes[u1].begin(); it != nodes[u1].end() && *it < c; it++) {
							//ans[*it][y - (r - 1) * c] = std::min(ans[*it][y - (r - 1) * c], k);
						//}
					//}
				//}
				//if (nodes[u1].size() < nodes[u2].size()) {
					//std::swap(nodes[u1], nodes[u2]);
				//}
				//for (int y : nodes[u2]) {
					//nodes[u1].insert(y);
				//}
				//if (reach[u1].size() < reach[u2].size()) {
					//std::swap(reach[u1], reach[u2]);
				//}
				//for (int y : reach[u2]) {
					//reach[u1].insert(y);
				//}
				//nodes[u2].clear();
				//reach[u2].clear();
				//dsu.unite(u2, u1);
			//}
		//}
	//}
//}



void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R;
	c = C;
	ans.resize(c, std::vector <int> (c));
	h.resize(r, std::vector <int> (c - 1));
	v.resize(r - 1, std::vector <int> (c));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (j < c - 1) {
				h[i][j] = H[i][j];
			}
			if (i < r - 1) {
				v[i][j] = V[i][j];
			}
		}
	}
	calculate();
}

void changeH(int p, int q, int w) {
	h[p][q] = w;
	calculate();
}

void changeV(int p, int q, int w) {
	v[p][q] = w;
	calculate();
}

int escape(int v1, int v2) {
	return ans[v1][v2];
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

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