oj.uz

Submission #211956

# Submission time Handle Problem Language Result Execution time Memory
211956 2020-03-21T20:11:20 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);

	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);
		}
		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)
	{
		encode(edges[i].size());
		for (auto u : edges[i])
			encode(u);
	}

	// 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)
	{
		int k = decode();
		for (int j = 0; j < k; ++j)
		{
			int a = decode();
			edges[i].emplace_back(a);
			edges[a].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 5276 ms 13808 KB Output is partially correct - 180830 call(s) of encode_bit()
2 Correct 10 ms 4560 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 69 ms 6192 KB Output is partially correct - 102010 call(s) of encode_bit()
4 Correct 11 ms 4832 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 97 ms 6728 KB Output is partially correct - 151710 call(s) of encode_bit()
6 Correct 100 ms 6952 KB Output is partially correct - 165360 call(s) of encode_bit()
7 Correct 192 ms 8228 KB Output is partially correct - 277870 call(s) of encode_bit()
8 Runtime error 2185 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 63 ms 5672 KB Output is correct - 50190 call(s) of encode_bit()
10 Correct 72 ms 5648 KB Output is correct - 57610 call(s) of encode_bit()
11 Correct 127 ms 6216 KB Output is partially correct - 102780 call(s) of encode_bit()
12 Correct 40 ms 5332 KB Output is correct - 21040 call(s) of encode_bit()
13 Correct 169 ms 7384 KB Output is partially correct - 153440 call(s) of encode_bit()
14 Execution timed out 10040 ms 37496 KB Time limit exceeded
15 Execution timed out 10100 ms 31832 KB Time limit exceeded
16 Execution timed out 10046 ms 36852 KB Time limit exceeded
17 Execution timed out 10042 ms 40904 KB Time limit exceeded
18 Execution timed out 10032 ms 41424 KB Time limit exceeded
19 Correct 4375 ms 67016 KB Output is partially correct - 166270 call(s) of encode_bit()
20 Correct 356 ms 7252 KB Output is partially correct - 113730 call(s) of encode_bit()
21 Correct 849 ms 11112 KB Output is partially correct - 133700 call(s) of encode_bit()
22 Correct 185 ms 8368 KB Output is partially correct - 239890 call(s) of encode_bit()
23 Correct 370 ms 8272 KB Output is partially correct - 178200 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5276 ms 13808 KB Output is partially correct - 180830 call(s) of encode_bit()
2 Correct 10 ms 4560 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 69 ms 6192 KB Output is partially correct - 102010 call(s) of encode_bit()
4 Correct 11 ms 4832 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 97 ms 6728 KB Output is partially correct - 151710 call(s) of encode_bit()
6 Correct 100 ms 6952 KB Output is partially correct - 165360 call(s) of encode_bit()
7 Correct 192 ms 8228 KB Output is partially correct - 277870 call(s) of encode_bit()
8 Runtime error 2185 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 63 ms 5672 KB Output is correct - 50190 call(s) of encode_bit()
10 Correct 72 ms 5648 KB Output is correct - 57610 call(s) of encode_bit()
11 Correct 127 ms 6216 KB Output is partially correct - 102780 call(s) of encode_bit()
12 Correct 40 ms 5332 KB Output is correct - 21040 call(s) of encode_bit()
13 Correct 169 ms 7384 KB Output is partially correct - 153440 call(s) of encode_bit()
14 Execution timed out 10040 ms 37496 KB Time limit exceeded
15 Execution timed out 10100 ms 31832 KB Time limit exceeded
16 Execution timed out 10046 ms 36852 KB Time limit exceeded
17 Execution timed out 10042 ms 40904 KB Time limit exceeded
18 Execution timed out 10032 ms 41424 KB Time limit exceeded
19 Correct 4375 ms 67016 KB Output is partially correct - 166270 call(s) of encode_bit()
20 Correct 356 ms 7252 KB Output is partially correct - 113730 call(s) of encode_bit()
21 Correct 849 ms 11112 KB Output is partially correct - 133700 call(s) of encode_bit()
22 Correct 185 ms 8368 KB Output is partially correct - 239890 call(s) of encode_bit()
23 Correct 370 ms 8272 KB Output is partially correct - 178200 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5276 ms 13808 KB Output is partially correct - 180830 call(s) of encode_bit()
2 Correct 10 ms 4560 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 69 ms 6192 KB Output is partially correct - 102010 call(s) of encode_bit()
4 Correct 11 ms 4832 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 97 ms 6728 KB Output is partially correct - 151710 call(s) of encode_bit()
6 Correct 100 ms 6952 KB Output is partially correct - 165360 call(s) of encode_bit()
7 Correct 192 ms 8228 KB Output is partially correct - 277870 call(s) of encode_bit()
8 Runtime error 2185 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 63 ms 5672 KB Output is correct - 50190 call(s) of encode_bit()
10 Correct 72 ms 5648 KB Output is correct - 57610 call(s) of encode_bit()
11 Correct 127 ms 6216 KB Output is partially correct - 102780 call(s) of encode_bit()
12 Correct 40 ms 5332 KB Output is correct - 21040 call(s) of encode_bit()
13 Correct 169 ms 7384 KB Output is partially correct - 153440 call(s) of encode_bit()
14 Execution timed out 10040 ms 37496 KB Time limit exceeded
15 Execution timed out 10100 ms 31832 KB Time limit exceeded
16 Execution timed out 10046 ms 36852 KB Time limit exceeded
17 Execution timed out 10042 ms 40904 KB Time limit exceeded
18 Execution timed out 10032 ms 41424 KB Time limit exceeded
19 Correct 4375 ms 67016 KB Output is partially correct - 166270 call(s) of encode_bit()
20 Correct 356 ms 7252 KB Output is partially correct - 113730 call(s) of encode_bit()
21 Correct 849 ms 11112 KB Output is partially correct - 133700 call(s) of encode_bit()
22 Correct 185 ms 8368 KB Output is partially correct - 239890 call(s) of encode_bit()
23 Correct 370 ms 8272 KB Output is partially correct - 178200 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5276 ms 13808 KB Output is partially correct - 180830 call(s) of encode_bit()
2 Correct 10 ms 4560 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 69 ms 6192 KB Output is partially correct - 102010 call(s) of encode_bit()
4 Correct 11 ms 4832 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 97 ms 6728 KB Output is partially correct - 151710 call(s) of encode_bit()
6 Correct 100 ms 6952 KB Output is partially correct - 165360 call(s) of encode_bit()
7 Correct 192 ms 8228 KB Output is partially correct - 277870 call(s) of encode_bit()
8 Runtime error 2185 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 63 ms 5672 KB Output is correct - 50190 call(s) of encode_bit()
10 Correct 72 ms 5648 KB Output is correct - 57610 call(s) of encode_bit()
11 Correct 127 ms 6216 KB Output is partially correct - 102780 call(s) of encode_bit()
12 Correct 40 ms 5332 KB Output is correct - 21040 call(s) of encode_bit()
13 Correct 169 ms 7384 KB Output is partially correct - 153440 call(s) of encode_bit()
14 Execution timed out 10040 ms 37496 KB Time limit exceeded
15 Execution timed out 10100 ms 31832 KB Time limit exceeded
16 Execution timed out 10046 ms 36852 KB Time limit exceeded
17 Execution timed out 10042 ms 40904 KB Time limit exceeded
18 Execution timed out 10032 ms 41424 KB Time limit exceeded
19 Correct 4375 ms 67016 KB Output is partially correct - 166270 call(s) of encode_bit()
20 Correct 356 ms 7252 KB Output is partially correct - 113730 call(s) of encode_bit()
21 Correct 849 ms 11112 KB Output is partially correct - 133700 call(s) of encode_bit()
22 Correct 185 ms 8368 KB Output is partially correct - 239890 call(s) of encode_bit()
23 Correct 370 ms 8272 KB Output is partially correct - 178200 call(s) of encode_bit()