oj.uz

Submission #211958

# Submission time Handle Problem Language Result Execution time Memory
211958 2020-03-21T20:24:07 Z mode149256 Saveit (IOI10_saveit) C++14
0 / 100
 10000 ms 262148 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);

		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;
					q.push(u);
				}
			}
		}

		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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5304 ms 13296 KB Output is correct - 36020 call(s) of encode_bit()
2 Correct 10 ms 4584 KB Output is correct - 35 call(s) of encode_bit()
3 Correct 76 ms 6556 KB Output is partially correct - 131280 call(s) of encode_bit()
4 Correct 11 ms 4692 KB Output is correct - 45 call(s) of encode_bit()
5 Correct 95 ms 6988 KB Output is partially correct - 176040 call(s) of encode_bit()
6 Correct 110 ms 7232 KB Output is partially correct - 193880 call(s) of encode_bit()
7 Correct 174 ms 8516 KB Output is partially correct - 293040 call(s) of encode_bit()
8 Runtime error 2132 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 63 ms 6096 KB Output is partially correct - 81920 call(s) of encode_bit()
10 Correct 71 ms 6108 KB Output is partially correct - 90080 call(s) of encode_bit()
11 Correct 131 ms 6584 KB Output is partially correct - 129780 call(s) of encode_bit()
12 Correct 44 ms 5712 KB Output is correct - 55960 call(s) of encode_bit()
13 Correct 183 ms 7700 KB Output is partially correct - 163660 call(s) of encode_bit()
14 Execution timed out 10051 ms 37892 KB Time limit exceeded
15 Execution timed out 10024 ms 32076 KB Time limit exceeded
16 Execution timed out 10050 ms 36800 KB Time limit exceeded
17 Execution timed out 10078 ms 40828 KB Time limit exceeded
18 Execution timed out 10038 ms 41828 KB Time limit exceeded
19 Correct 4375 ms 67816 KB Output is partially correct - 186700 call(s) of encode_bit()
20 Correct 351 ms 7608 KB Output is partially correct - 113960 call(s) of encode_bit()
21 Correct 842 ms 11360 KB Output is partially correct - 137760 call(s) of encode_bit()
22 Correct 187 ms 8388 KB Output is partially correct - 248180 call(s) of encode_bit()
23 Correct 373 ms 8324 KB Output is partially correct - 165260 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5304 ms 13296 KB Output is correct - 36020 call(s) of encode_bit()
2 Correct 10 ms 4584 KB Output is correct - 35 call(s) of encode_bit()
3 Correct 76 ms 6556 KB Output is partially correct - 131280 call(s) of encode_bit()
4 Correct 11 ms 4692 KB Output is correct - 45 call(s) of encode_bit()
5 Correct 95 ms 6988 KB Output is partially correct - 176040 call(s) of encode_bit()
6 Correct 110 ms 7232 KB Output is partially correct - 193880 call(s) of encode_bit()
7 Correct 174 ms 8516 KB Output is partially correct - 293040 call(s) of encode_bit()
8 Runtime error 2132 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 63 ms 6096 KB Output is partially correct - 81920 call(s) of encode_bit()
10 Correct 71 ms 6108 KB Output is partially correct - 90080 call(s) of encode_bit()
11 Correct 131 ms 6584 KB Output is partially correct - 129780 call(s) of encode_bit()
12 Correct 44 ms 5712 KB Output is correct - 55960 call(s) of encode_bit()
13 Correct 183 ms 7700 KB Output is partially correct - 163660 call(s) of encode_bit()
14 Execution timed out 10051 ms 37892 KB Time limit exceeded
15 Execution timed out 10024 ms 32076 KB Time limit exceeded
16 Execution timed out 10050 ms 36800 KB Time limit exceeded
17 Execution timed out 10078 ms 40828 KB Time limit exceeded
18 Execution timed out 10038 ms 41828 KB Time limit exceeded
19 Correct 4375 ms 67816 KB Output is partially correct - 186700 call(s) of encode_bit()
20 Correct 351 ms 7608 KB Output is partially correct - 113960 call(s) of encode_bit()
21 Correct 842 ms 11360 KB Output is partially correct - 137760 call(s) of encode_bit()
22 Correct 187 ms 8388 KB Output is partially correct - 248180 call(s) of encode_bit()
23 Correct 373 ms 8324 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 5304 ms 13296 KB Output is correct - 36020 call(s) of encode_bit()
2 Correct 10 ms 4584 KB Output is correct - 35 call(s) of encode_bit()
3 Correct 76 ms 6556 KB Output is partially correct - 131280 call(s) of encode_bit()
4 Correct 11 ms 4692 KB Output is correct - 45 call(s) of encode_bit()
5 Correct 95 ms 6988 KB Output is partially correct - 176040 call(s) of encode_bit()
6 Correct 110 ms 7232 KB Output is partially correct - 193880 call(s) of encode_bit()
7 Correct 174 ms 8516 KB Output is partially correct - 293040 call(s) of encode_bit()
8 Runtime error 2132 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 63 ms 6096 KB Output is partially correct - 81920 call(s) of encode_bit()
10 Correct 71 ms 6108 KB Output is partially correct - 90080 call(s) of encode_bit()
11 Correct 131 ms 6584 KB Output is partially correct - 129780 call(s) of encode_bit()
12 Correct 44 ms 5712 KB Output is correct - 55960 call(s) of encode_bit()
13 Correct 183 ms 7700 KB Output is partially correct - 163660 call(s) of encode_bit()
14 Execution timed out 10051 ms 37892 KB Time limit exceeded
15 Execution timed out 10024 ms 32076 KB Time limit exceeded
16 Execution timed out 10050 ms 36800 KB Time limit exceeded
17 Execution timed out 10078 ms 40828 KB Time limit exceeded
18 Execution timed out 10038 ms 41828 KB Time limit exceeded
19 Correct 4375 ms 67816 KB Output is partially correct - 186700 call(s) of encode_bit()
20 Correct 351 ms 7608 KB Output is partially correct - 113960 call(s) of encode_bit()
21 Correct 842 ms 11360 KB Output is partially correct - 137760 call(s) of encode_bit()
22 Correct 187 ms 8388 KB Output is partially correct - 248180 call(s) of encode_bit()
23 Correct 373 ms 8324 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 5304 ms 13296 KB Output is correct - 36020 call(s) of encode_bit()
2 Correct 10 ms 4584 KB Output is correct - 35 call(s) of encode_bit()
3 Correct 76 ms 6556 KB Output is partially correct - 131280 call(s) of encode_bit()
4 Correct 11 ms 4692 KB Output is correct - 45 call(s) of encode_bit()
5 Correct 95 ms 6988 KB Output is partially correct - 176040 call(s) of encode_bit()
6 Correct 110 ms 7232 KB Output is partially correct - 193880 call(s) of encode_bit()
7 Correct 174 ms 8516 KB Output is partially correct - 293040 call(s) of encode_bit()
8 Runtime error 2132 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 63 ms 6096 KB Output is partially correct - 81920 call(s) of encode_bit()
10 Correct 71 ms 6108 KB Output is partially correct - 90080 call(s) of encode_bit()
11 Correct 131 ms 6584 KB Output is partially correct - 129780 call(s) of encode_bit()
12 Correct 44 ms 5712 KB Output is correct - 55960 call(s) of encode_bit()
13 Correct 183 ms 7700 KB Output is partially correct - 163660 call(s) of encode_bit()
14 Execution timed out 10051 ms 37892 KB Time limit exceeded
15 Execution timed out 10024 ms 32076 KB Time limit exceeded
16 Execution timed out 10050 ms 36800 KB Time limit exceeded
17 Execution timed out 10078 ms 40828 KB Time limit exceeded
18 Execution timed out 10038 ms 41828 KB Time limit exceeded
19 Correct 4375 ms 67816 KB Output is partially correct - 186700 call(s) of encode_bit()
20 Correct 351 ms 7608 KB Output is partially correct - 113960 call(s) of encode_bit()
21 Correct 842 ms 11360 KB Output is partially correct - 137760 call(s) of encode_bit()
22 Correct 187 ms 8388 KB Output is partially correct - 248180 call(s) of encode_bit()
23 Correct 373 ms 8324 KB Output is partially correct - 165260 call(s) of encode_bit()