oj.uz

Submission #211960

# Submission time Handle Problem Language Result Execution time Memory
211960 2020-03-21T20:28:10 Z mode149256 Saveit (IOI10_saveit) C++14
50 / 100
 394 ms 12528 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}


void encode(int nv, int nh, int ne, int *v1, int *v2) {
	int N = nv;
	int H = nh;
	int P = ne;
	vii edges(N);
	vii visos(N);

	vii yra(H, vi(N, 0));

	for (int i = 0; i < P; ++i)
	{
		int a = v1[i];
		int b = v2[i];
		if (a < H or b < H) {
			edges[a].emplace_back(b);
			edges[b].emplace_back(a);
			if (a >= H) swap(a, b);
			yra[a][b] = 1;
		}
		visos[a].emplace_back(b);
		visos[b].emplace_back(a);
	}

	auto encode = [&](int a) {
		// printf("encodinu a = %d\n", a);
		for (int i = 0; i < 10; ++i)
			encode_bit((a >> i) & 1);
	};

	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			encode_bit(yra[i][j]);
		}
	}
	// do stuff // send edges

	vii fast(H, vi(N, MOD));

	auto bfs = [&](int start, vi & dis) {
		dis = vi(N, MOD);
		dis[start] = 0;
		queue<int> q;
		q.push(start);
		while (q.size()) {
			int c = q.front(); q.pop();
			for (auto u : edges[c]) {
				if (dis[c] + 1 < dis[u]) {
					dis[u] = dis[c] + 1;
					q.push(u);
				}
			}
		}
	};

	// O(H*N)
	auto upd = [&](int prad) {
		for (int i = prad; i < H; ++i)
			bfs(i, fast[i]);
	};


	upd(0);

	vpi augmeting;
	auto add_edge = [&](int a, int b) {
		edges[a].emplace_back(b);
		edges[b].emplace_back(a);
		augmeting.emplace_back(a, b);
	};


	for (int i = 0; i < H; ++i)
	{
		queue<int> q;
		q.push(i);
		vb been(N, false);
		been[i] = true;

		while (q.size()) {
			int c = q.front(); q.pop();
			for (auto u : visos[c]) {
				if (fast[i][c] + 1 <= fast[i][u]) {
					if (fast[i][c] + 1 < fast[i][u]) add_edge(c, u);

					fast[i][u] = fast[i][c] + 1;
					if (!been[u])
						q.push(u);

					been[u] = true;
				}
			}
		}

		upd(i + 1);
	}

	augmeting.emplace_back(1011, 1011);

	for (auto u : augmeting) {
		// printf("encodinau %d %d\n", u.x, u.y);
		encode(u.x);
		encode(u.y);
	}
	return;
}

#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

void decode(int nv, int nh) {
	int N = nv;
	int H = nh;

	auto decode = [&]() -> int {
		int ret = 0;
		for (int i = 0; i < 10; ++i)
		{
			ret |= (decode_bit() << i);
		}
		// printf("decodinu %d\n", ret);
		return ret;
	};

	vii edges(N);

	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (decode_bit()) {
				edges[i].emplace_back(j);
				edges[j].emplace_back(i);
			}
		}
	}
	
	{

		int a = decode();
		int b = decode();
		while (a != 1011) {
			edges[a].emplace_back(b);
			edges[b].emplace_back(a);
			a = decode();
			b = decode();
		};
	}

	for (int i = 0; i < H; ++i)
	{
		vi dis(N, MOD);
		dis[i] = 0;
		queue<int> q;
		q.push(i);
		while (q.size()) {
			int c = q.front(); q.pop();
			for (auto u : edges[c]) {
				if (dis[c] + 1 < dis[u]) {
					dis[u] = dis[c] + 1;
					q.push(u);
				}
			}
		}

		for (int j = 0; j < N; ++j)
		{
			hops(i, j, dis[j]);
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 12528 KB Output is correct - 36020 call(s) of encode_bit()
2 Correct 10 ms 4760 KB Output is correct - 35 call(s) of encode_bit()
3 Correct 73 ms 6600 KB Output is partially correct - 131280 call(s) of encode_bit()
4 Correct 10 ms 4820 KB Output is correct - 45 call(s) of encode_bit()
5 Correct 87 ms 7080 KB Output is partially correct - 176040 call(s) of encode_bit()
6 Correct 93 ms 7156 KB Output is partially correct - 193880 call(s) of encode_bit()
7 Correct 145 ms 8576 KB Output is partially correct - 293040 call(s) of encode_bit()
8 Correct 64 ms 6088 KB Output is partially correct - 107136 call(s) of encode_bit()
9 Correct 60 ms 5968 KB Output is partially correct - 81920 call(s) of encode_bit()
10 Correct 54 ms 5960 KB Output is partially correct - 90080 call(s) of encode_bit()
11 Correct 76 ms 6688 KB Output is partially correct - 129780 call(s) of encode_bit()
12 Correct 44 ms 5612 KB Output is correct - 55960 call(s) of encode_bit()
13 Correct 114 ms 7404 KB Output is partially correct - 163660 call(s) of encode_bit()
14 Correct 54 ms 6036 KB Output is partially correct - 82280 call(s) of encode_bit()
15 Correct 60 ms 6016 KB Output is partially correct - 79820 call(s) of encode_bit()
16 Correct 107 ms 7360 KB Output is partially correct - 134140 call(s) of encode_bit()
17 Correct 88 ms 6604 KB Output is partially correct - 92780 call(s) of encode_bit()
18 Correct 114 ms 7320 KB Output is partially correct - 132360 call(s) of encode_bit()
19 Correct 97 ms 7364 KB Output is partially correct - 186700 call(s) of encode_bit()
20 Correct 115 ms 7264 KB Output is partially correct - 113960 call(s) of encode_bit()
21 Correct 145 ms 7812 KB Output is partially correct - 137760 call(s) of encode_bit()
22 Correct 135 ms 8364 KB Output is partially correct - 248180 call(s) of encode_bit()
23 Correct 157 ms 8440 KB Output is partially correct - 165260 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 12528 KB Output is correct - 36020 call(s) of encode_bit()
2 Correct 10 ms 4760 KB Output is correct - 35 call(s) of encode_bit()
3 Correct 73 ms 6600 KB Output is partially correct - 131280 call(s) of encode_bit()
4 Correct 10 ms 4820 KB Output is correct - 45 call(s) of encode_bit()
5 Correct 87 ms 7080 KB Output is partially correct - 176040 call(s) of encode_bit()
6 Correct 93 ms 7156 KB Output is partially correct - 193880 call(s) of encode_bit()
7 Correct 145 ms 8576 KB Output is partially correct - 293040 call(s) of encode_bit()
8 Correct 64 ms 6088 KB Output is partially correct - 107136 call(s) of encode_bit()
9 Correct 60 ms 5968 KB Output is partially correct - 81920 call(s) of encode_bit()
10 Correct 54 ms 5960 KB Output is partially correct - 90080 call(s) of encode_bit()
11 Correct 76 ms 6688 KB Output is partially correct - 129780 call(s) of encode_bit()
12 Correct 44 ms 5612 KB Output is correct - 55960 call(s) of encode_bit()
13 Correct 114 ms 7404 KB Output is partially correct - 163660 call(s) of encode_bit()
14 Correct 54 ms 6036 KB Output is partially correct - 82280 call(s) of encode_bit()
15 Correct 60 ms 6016 KB Output is partially correct - 79820 call(s) of encode_bit()
16 Correct 107 ms 7360 KB Output is partially correct - 134140 call(s) of encode_bit()
17 Correct 88 ms 6604 KB Output is partially correct - 92780 call(s) of encode_bit()
18 Correct 114 ms 7320 KB Output is partially correct - 132360 call(s) of encode_bit()
19 Correct 97 ms 7364 KB Output is partially correct - 186700 call(s) of encode_bit()
20 Correct 115 ms 7264 KB Output is partially correct - 113960 call(s) of encode_bit()
21 Correct 145 ms 7812 KB Output is partially correct - 137760 call(s) of encode_bit()
22 Correct 135 ms 8364 KB Output is partially correct - 248180 call(s) of encode_bit()
23 Correct 157 ms 8440 KB Output is partially correct - 165260 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 12528 KB Output is correct - 36020 call(s) of encode_bit()
2 Correct 10 ms 4760 KB Output is correct - 35 call(s) of encode_bit()
3 Correct 73 ms 6600 KB Output is partially correct - 131280 call(s) of encode_bit()
4 Correct 10 ms 4820 KB Output is correct - 45 call(s) of encode_bit()
5 Correct 87 ms 7080 KB Output is partially correct - 176040 call(s) of encode_bit()
6 Correct 93 ms 7156 KB Output is partially correct - 193880 call(s) of encode_bit()
7 Correct 145 ms 8576 KB Output is partially correct - 293040 call(s) of encode_bit()
8 Correct 64 ms 6088 KB Output is partially correct - 107136 call(s) of encode_bit()
9 Correct 60 ms 5968 KB Output is partially correct - 81920 call(s) of encode_bit()
10 Correct 54 ms 5960 KB Output is partially correct - 90080 call(s) of encode_bit()
11 Correct 76 ms 6688 KB Output is partially correct - 129780 call(s) of encode_bit()
12 Correct 44 ms 5612 KB Output is correct - 55960 call(s) of encode_bit()
13 Correct 114 ms 7404 KB Output is partially correct - 163660 call(s) of encode_bit()
14 Correct 54 ms 6036 KB Output is partially correct - 82280 call(s) of encode_bit()
15 Correct 60 ms 6016 KB Output is partially correct - 79820 call(s) of encode_bit()
16 Correct 107 ms 7360 KB Output is partially correct - 134140 call(s) of encode_bit()
17 Correct 88 ms 6604 KB Output is partially correct - 92780 call(s) of encode_bit()
18 Correct 114 ms 7320 KB Output is partially correct - 132360 call(s) of encode_bit()
19 Correct 97 ms 7364 KB Output is partially correct - 186700 call(s) of encode_bit()
20 Correct 115 ms 7264 KB Output is partially correct - 113960 call(s) of encode_bit()
21 Correct 145 ms 7812 KB Output is partially correct - 137760 call(s) of encode_bit()
22 Correct 135 ms 8364 KB Output is partially correct - 248180 call(s) of encode_bit()
23 Correct 157 ms 8440 KB Output is partially correct - 165260 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 12528 KB Output is correct - 36020 call(s) of encode_bit()
2 Correct 10 ms 4760 KB Output is correct - 35 call(s) of encode_bit()
3 Correct 73 ms 6600 KB Output is partially correct - 131280 call(s) of encode_bit()
4 Correct 10 ms 4820 KB Output is correct - 45 call(s) of encode_bit()
5 Correct 87 ms 7080 KB Output is partially correct - 176040 call(s) of encode_bit()
6 Correct 93 ms 7156 KB Output is partially correct - 193880 call(s) of encode_bit()
7 Correct 145 ms 8576 KB Output is partially correct - 293040 call(s) of encode_bit()
8 Correct 64 ms 6088 KB Output is partially correct - 107136 call(s) of encode_bit()
9 Correct 60 ms 5968 KB Output is partially correct - 81920 call(s) of encode_bit()
10 Correct 54 ms 5960 KB Output is partially correct - 90080 call(s) of encode_bit()
11 Correct 76 ms 6688 KB Output is partially correct - 129780 call(s) of encode_bit()
12 Correct 44 ms 5612 KB Output is correct - 55960 call(s) of encode_bit()
13 Correct 114 ms 7404 KB Output is partially correct - 163660 call(s) of encode_bit()
14 Correct 54 ms 6036 KB Output is partially correct - 82280 call(s) of encode_bit()
15 Correct 60 ms 6016 KB Output is partially correct - 79820 call(s) of encode_bit()
16 Correct 107 ms 7360 KB Output is partially correct - 134140 call(s) of encode_bit()
17 Correct 88 ms 6604 KB Output is partially correct - 92780 call(s) of encode_bit()
18 Correct 114 ms 7320 KB Output is partially correct - 132360 call(s) of encode_bit()
19 Correct 97 ms 7364 KB Output is partially correct - 186700 call(s) of encode_bit()
20 Correct 115 ms 7264 KB Output is partially correct - 113960 call(s) of encode_bit()
21 Correct 145 ms 7812 KB Output is partially correct - 137760 call(s) of encode_bit()
22 Correct 135 ms 8364 KB Output is partially correct - 248180 call(s) of encode_bit()
23 Correct 157 ms 8440 KB Output is partially correct - 165260 call(s) of encode_bit()