oj.uz

Submission #1061511

# Submission time Handle Problem Language Result Execution time Memory
1061511 2024-08-16T10:20:07 Z thieunguyenhuy Saveit (IOI10_saveit) C++17
0 / 100
 139 ms 19108 KB 
#ifndef hwe
	#include "grader.h"
#endif

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

#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 1000, H = 36;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;

int dist[H][N], par[N];
vector<int> adj[N];

#ifdef hwe
void encode_bit(int bit) {
	cerr << bit;
}
#endif

void bfs(int root) {
	memset(dist[root], 0x3f, sizeof dist[root]);
	queue<int> q; q.emplace(root); dist[root][root] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto v : adj[u]) if (minimize(dist[root][v], dist[root][u] + 1)) {
			q.emplace(v);
			if (root == 0) par[v] = u;
		}
	}
}

void encode(int n, int h, int m, int *a, int *b) {
	for (int i = 0; i < n; ++i) {
		adj[i].clear(), par[i] = -1;
	}
	int LOG = lg(n) + 1;

	for (int i = 0; i < m; ++i) {
		int u = a[i], v = b[i];
		adj[u].emplace_back(v), adj[v].emplace_back(u);
	}

	for (int i = 0; i < h; ++i) bfs(i);

	// send the spanning tree by the parent of each node in the tree
	for (int i = 1; i < n; ++i)  for (int j = LOG - 1; j >= 0; --j) {
		encode_bit(BIT(par[i], j));
	}
	// cerr << "Done tree\n";

	for (int hub = 0; hub < h; ++hub) {
		for (int i = 1; i < n; i += 3) {
			int num = 0, cnt = 0;
			for (int j = i; j < min(i + 3, n); ++j) {
				int send = dist[hub][j] - dist[hub][par[j]] + 1;
				num = num * 3 + send, ++cnt;
			}
			while (cnt < 3) num = num * 3, ++cnt;
			for (int j = 4; j >= 0; --j) encode_bit(BIT(num, j));
		}
	}
}

#ifdef hwe
signed main() {
	int n = 3, h = 1, m = 2;
	int a[m], b[m];
	a[0] = 0, b[0] = 1;
	a[1] = 0, b[1] = 2;

	encode(n, h, m, a, b);

    cerr << '\n'; return 0;
}
#endif

#ifndef hwe
	#include "grader.h"
#endif

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

#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 1000, H = 36;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;

int dep[N], par[N], dif[N], dist[N];
vector<int> adj[N];
string encoding;
int pos = 0;

#ifdef hwe
int decode_bit() {
	// cerr << pos << ' ' << encoding[pos] << '\n';
	return encoding[pos++] - 48;
}

void hops(int u, int v, int d) {
	cerr << "Dist " << u << ' ' << v << ' ' << d << '\n';
}
#endif

void decode(int n, int h) {
	for (int i = 0; i < n; ++i) {
		adj[i].clear(), dep[i] = -1, par[i] = 0;
	}
	int LOG = lg(n) + 1;
	// cerr << LOG << '\n';

	for (int i = 1; i < n; ++i) {
		par[i] = 0;
		for (int j = LOG - 1; j >= 0; --j) par[i] = par[i] << 1 | decode_bit();
		// cerr << "Par " << i << ' ' << par[i] << '\n';
		adj[par[i]].emplace_back(i);
	}

	queue<int> q; q.emplace(0); dep[0] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto v : adj[u]) if (dep[v] == -1) {
			dep[v] = dep[u] + 1;
			q.emplace(v);
		}
	}

	vector<int> order(n - 1); iota(order.begin(), order.end(), 1);
	sort (order.begin(), order.end(), [&](int x, int y) {
		return dep[x] < dep[y];
	});

	for (int hub = 0; hub < h; ++hub) {
		memset(dist, -1, sizeof dist);
		dist[hub] = 0;
		
		for (int i = 1; i < n; i += 3) {
			int num = 0;
			for (int j = 4; j >= 0; --j) num = num << 1 | decode_bit();
			// cerr << "Num: " << num << '\n';
			vector<int> sends;
			while (num > 0) sends.emplace_back(num % 3), num /= 3;
			reverse(sends.begin(), sends.end());
			// cerr << "Send: ";
			// for (auto &x : sends) cerr << x << ' ';
			// cerr << '\n';
			for (int j = i; j < min(i + 3, n); ++j) dif[j] = sends[j - i] - 1;
		}

		int u = hub;
		while (u != 0) {
			dist[par[u]] = dist[u] - dif[u];
			u = par[u];
		}

		assert(dist[0] != -1);

		for (auto u : order) {
			if (dist[u] != -1) continue;
			dist[u] = dist[par[u]] + dif[u];
		}

		for (int i = 0; i < n; ++i) hops(hub, i, dist[i]);
	}
}

#ifdef hwe
signed main() {
	cin >> encoding; pos = 0;
	cerr << encoding << '\n';
	decode(3, 1);

    cerr << '\n'; return 0;
}
#endif

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 16592 KB wrong parameter
2 Incorrect 2 ms 11264 KB wrong parameter
3 Runtime error 15 ms 16128 KB Execution killed with signal 11
4 Incorrect 2 ms 11268 KB wrong parameter
5 Runtime error 17 ms 16372 KB Execution killed with signal 11
6 Runtime error 19 ms 16128 KB Execution killed with signal 11
7 Incorrect 27 ms 11888 KB wrong parameter
8 Runtime error 14 ms 16016 KB Execution killed with signal 11
9 Incorrect 12 ms 11520 KB wrong parameter
10 Incorrect 11 ms 11524 KB wrong parameter
11 Runtime error 17 ms 16136 KB Execution killed with signal 11
12 Runtime error 15 ms 16012 KB Execution killed with signal 11
13 Incorrect 27 ms 12012 KB wrong parameter
14 Incorrect 12 ms 11524 KB wrong parameter
15 Runtime error 18 ms 16140 KB Execution killed with signal 11
16 Runtime error 30 ms 16276 KB Execution killed with signal 11
17 Runtime error 26 ms 16364 KB Execution killed with signal 11
18 Runtime error 33 ms 16556 KB Execution killed with signal 6
19 Runtime error 22 ms 16384 KB Execution killed with signal 6
20 Runtime error 41 ms 18928 KB Execution killed with signal 11
21 Incorrect 40 ms 14300 KB wrong parameter
22 Incorrect 27 ms 12032 KB wrong parameter
23 Runtime error 48 ms 19108 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 16592 KB wrong parameter
2 Incorrect 2 ms 11264 KB wrong parameter
3 Runtime error 15 ms 16128 KB Execution killed with signal 11
4 Incorrect 2 ms 11268 KB wrong parameter
5 Runtime error 17 ms 16372 KB Execution killed with signal 11
6 Runtime error 19 ms 16128 KB Execution killed with signal 11
7 Incorrect 27 ms 11888 KB wrong parameter
8 Runtime error 14 ms 16016 KB Execution killed with signal 11
9 Incorrect 12 ms 11520 KB wrong parameter
10 Incorrect 11 ms 11524 KB wrong parameter
11 Runtime error 17 ms 16136 KB Execution killed with signal 11
12 Runtime error 15 ms 16012 KB Execution killed with signal 11
13 Incorrect 27 ms 12012 KB wrong parameter
14 Incorrect 12 ms 11524 KB wrong parameter
15 Runtime error 18 ms 16140 KB Execution killed with signal 11
16 Runtime error 30 ms 16276 KB Execution killed with signal 11
17 Runtime error 26 ms 16364 KB Execution killed with signal 11
18 Runtime error 33 ms 16556 KB Execution killed with signal 6
19 Runtime error 22 ms 16384 KB Execution killed with signal 6
20 Runtime error 41 ms 18928 KB Execution killed with signal 11
21 Incorrect 40 ms 14300 KB wrong parameter
22 Incorrect 27 ms 12032 KB wrong parameter
23 Runtime error 48 ms 19108 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 16592 KB wrong parameter
2 Incorrect 2 ms 11264 KB wrong parameter
3 Runtime error 15 ms 16128 KB Execution killed with signal 11
4 Incorrect 2 ms 11268 KB wrong parameter
5 Runtime error 17 ms 16372 KB Execution killed with signal 11
6 Runtime error 19 ms 16128 KB Execution killed with signal 11
7 Incorrect 27 ms 11888 KB wrong parameter
8 Runtime error 14 ms 16016 KB Execution killed with signal 11
9 Incorrect 12 ms 11520 KB wrong parameter
10 Incorrect 11 ms 11524 KB wrong parameter
11 Runtime error 17 ms 16136 KB Execution killed with signal 11
12 Runtime error 15 ms 16012 KB Execution killed with signal 11
13 Incorrect 27 ms 12012 KB wrong parameter
14 Incorrect 12 ms 11524 KB wrong parameter
15 Runtime error 18 ms 16140 KB Execution killed with signal 11
16 Runtime error 30 ms 16276 KB Execution killed with signal 11
17 Runtime error 26 ms 16364 KB Execution killed with signal 11
18 Runtime error 33 ms 16556 KB Execution killed with signal 6
19 Runtime error 22 ms 16384 KB Execution killed with signal 6
20 Runtime error 41 ms 18928 KB Execution killed with signal 11
21 Incorrect 40 ms 14300 KB wrong parameter
22 Incorrect 27 ms 12032 KB wrong parameter
23 Runtime error 48 ms 19108 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 16592 KB wrong parameter
2 Incorrect 2 ms 11264 KB wrong parameter
3 Runtime error 15 ms 16128 KB Execution killed with signal 11
4 Incorrect 2 ms 11268 KB wrong parameter
5 Runtime error 17 ms 16372 KB Execution killed with signal 11
6 Runtime error 19 ms 16128 KB Execution killed with signal 11
7 Incorrect 27 ms 11888 KB wrong parameter
8 Runtime error 14 ms 16016 KB Execution killed with signal 11
9 Incorrect 12 ms 11520 KB wrong parameter
10 Incorrect 11 ms 11524 KB wrong parameter
11 Runtime error 17 ms 16136 KB Execution killed with signal 11
12 Runtime error 15 ms 16012 KB Execution killed with signal 11
13 Incorrect 27 ms 12012 KB wrong parameter
14 Incorrect 12 ms 11524 KB wrong parameter
15 Runtime error 18 ms 16140 KB Execution killed with signal 11
16 Runtime error 30 ms 16276 KB Execution killed with signal 11
17 Runtime error 26 ms 16364 KB Execution killed with signal 11
18 Runtime error 33 ms 16556 KB Execution killed with signal 6
19 Runtime error 22 ms 16384 KB Execution killed with signal 6
20 Runtime error 41 ms 18928 KB Execution killed with signal 11
21 Incorrect 40 ms 14300 KB wrong parameter
22 Incorrect 27 ms 12032 KB wrong parameter
23 Runtime error 48 ms 19108 KB Execution killed with signal 11