oj.uz

Submission #590345

# Submission time Handle Problem Language Result Execution time Memory
590345 2022-07-05T21:10:39 Z Temmie Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 9520 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx2,tune=native")

#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 * 100> 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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4564 KB Output is correct
2 Correct 56 ms 4668 KB Output is correct
3 Correct 118 ms 6192 KB Output is correct
4 Correct 55 ms 4564 KB Output is correct
5 Correct 55 ms 4668 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 432 KB Output is correct
11 Correct 64 ms 1284 KB Output is correct
12 Correct 2 ms 340 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20098 ms 720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 8724 KB Output is correct
2 Correct 1433 ms 8748 KB Output is correct
3 Correct 773 ms 8848 KB Output is correct
4 Correct 847 ms 9520 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20021 ms 664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20097 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -